{"id":"lookup-abstractions-enable-linear-time-across-paradigms","text":"The three lookup abstractions (Counter, set, binary search) are the mechanism that converts preprocessing investment into linear-time scans across both paradigms: hash preprocessing enables O(1) per-query lookups while sort preprocessing enables O(log n) binary search, and both reduce what would be O(n²) nested iteration to O(n) or O(n log n) single-pass scans.","truth_value":"IN","source":"","source_url":"","source_hash":"","justifications":[{"type":"SL","antecedents":["lookup-abstraction-trio-covers-all-queries","sorted-order-enables-all-efficient-search"],"outlist":[],"label":"The trio bridges preprocessing and scanning — without these abstractions, preprocessing would not improve asymptotic complexity of the scan phase"}],"dependents":["lookup-abstractions-instantiate-pipeline-phases"],"metadata":{"last_reviewed":"2026-06-07T22:02:22","review_result":"pass"},"created_at":"","updated_at":"","reviewed_at":"","verified_at":"","retracted_at":"","explanation":{"steps":[{"node":"lookup-abstractions-enable-linear-time-across-paradigms","truth_value":"IN","reason":"SL justification valid","antecedents":["lookup-abstraction-trio-covers-all-queries","sorted-order-enables-all-efficient-search"],"label":"The trio bridges preprocessing and scanning — without these abstractions, preprocessing would not improve asymptotic complexity of the scan phase"},{"node":"lookup-abstraction-trio-covers-all-queries","truth_value":"IN","reason":"SL justification valid","antecedents":["counter-universal-frequency-primitive","set-for-o1-membership-universal","binary-search-variants-share-convergence-structure"],"label":"Three abstractions partition the query-type space with no overlap and no gaps"},{"node":"counter-universal-frequency-primitive","truth_value":"IN","reason":"SL justification valid","antecedents":["counter-dominant-frequency-tool","counter-pattern-dominates-frequency-problems","counter-missing-key-returns-zero","counter-subtraction-drops-nonpositive"],"label":"Counter's built-in semantics eliminate boilerplate that manual dicts would require"},{"node":"counter-dominant-frequency-tool","truth_value":"IN","reason":"premise"},{"node":"counter-pattern-dominates-frequency-problems","truth_value":"IN","reason":"premise"},{"node":"counter-missing-key-returns-zero","truth_value":"IN","reason":"premise"},{"node":"counter-subtraction-drops-nonpositive","truth_value":"IN","reason":"premise"},{"node":"set-for-o1-membership-universal","truth_value":"IN","reason":"SL justification valid","antecedents":["set-conversion-before-loop-for-o1-lookup","k-distant-uses-set-dedup","find-difference-set-minus-idiom","two-out-of-three-set-algebra"],"label":"Set algebra (intersection, difference, membership) replaces manual iteration wherever applicable"},{"node":"set-conversion-before-loop-for-o1-lookup","truth_value":"IN","reason":"premise"},{"node":"k-distant-uses-set-dedup","truth_value":"IN","reason":"premise"},{"node":"find-difference-set-minus-idiom","truth_value":"IN","reason":"premise"},{"node":"two-out-of-three-set-algebra","truth_value":"IN","reason":"premise"},{"node":"binary-search-variants-share-convergence-structure","truth_value":"IN","reason":"SL justification valid","antecedents":["binary-search-on-derived-quantities-pattern","binary-search-on-value-pattern","left-biased-binary-search-pattern","fixed-point-uses-leftmost-binary-search"],"label":"the four patterns are orthogonal specializations of one template — search-target and bias are independent choices, and recognizing the shared structure reveals that any new binary search problem maps to a point in this 2D design space"},{"node":"binary-search-on-derived-quantities-pattern","truth_value":"IN","reason":"premise"},{"node":"binary-search-on-value-pattern","truth_value":"IN","reason":"premise"},{"node":"left-biased-binary-search-pattern","truth_value":"IN","reason":"premise"},{"node":"fixed-point-uses-leftmost-binary-search","truth_value":"IN","reason":"premise"},{"node":"sorted-order-enables-all-efficient-search","truth_value":"IN","reason":"SL justification valid","antecedents":["sort-preprocessing-enables-linear-scan","binary-search-variants-share-convergence-structure"],"label":"Sorting is the shared upstream step; linear scan and binary search are the two downstream consumers that exploit the monotonicity it establishes, covering the full spectrum from exhaustive to targeted search"},{"node":"sort-preprocessing-enables-linear-scan","truth_value":"IN","reason":"SL justification valid","antecedents":["sort-then-two-pointer-pattern","meeting-rooms-sort-then-scan","array-partition-sort-greedy","subsequence-limited-sum-greedy-sort"],"label":"Sorting is the universal complexity bridge from quadratic brute-force to n-log-n solutions"},{"node":"sort-then-two-pointer-pattern","truth_value":"IN","reason":"premise"},{"node":"meeting-rooms-sort-then-scan","truth_value":"IN","reason":"premise"},{"node":"array-partition-sort-greedy","truth_value":"IN","reason":"premise"},{"node":"subsequence-limited-sum-greedy-sort","truth_value":"IN","reason":"premise"}]}}