DSA FOUNDATION
Hashing foundations: identity, frequency, and boundaries
Choose exactly the information a key must retain: presence, an index, a frequency, or a run boundary.
Mechanism and state
A HashSet<Integer> answers whether an int value has occurred; a Map<Integer,Integer> can preserve the first index for Two Sum; a Map<Long,Long> stores prefix multiplicities for interval counts. These are different state contracts. Java generics require boxed reference types such as Integer, not int. Equality and hashCode must agree for custom keys; mutable key fields can make a stored entry unreachable by later lookup. Expected constant-time membership relies on a hash-table model and does not remove the cost of hashing long strings or compound keys. Single Number illustrates when a strong frequency promise permits replacing a map with a fixed-width XOR parity fold. Every paired bit pattern cancels, leaving the singleton; the fold does not validate the frequency promise. In LRU Cache, a key maps to its exact recency-list node rather than merely a value or array position. Mutable links belong to the mapped object; the int key itself remains stable. The list contributes eviction order that an ordinary hash map does not provide.
Why the pattern works
Write the exact processed-prefix meaning before coding. For Two Sum, query earlier positions before inserting the current value, preventing self-use. For exact-sum counts, seed zero once and query before recording the new boundary, preventing empty-subarray matches. For Longest Consecutive, iterate distinct values and launch a scan only at a missing predecessor; each maximal run has exactly one owner. A nested scan is expected linear only because run ownership avoids repeating work. Associativity and commutativity group promised duplicate pairs, each yielding zero, while the singleton survives the identity operation. An odd-length counterexample such as [1,2,3] shows why shape validation alone does not establish the multiplicity condition. Cache membership must agree in both the map and linked list. Removing an LRU victim requires deleting its key and unlinking its exact node; promoting a hit changes order without changing membership or node identity. Expected map costs combine with constant local pointer work.
Work through an example
Compare three uses of duplicates. [3,3] needs two distinct indices for target 6, so store an earlier index before matching the second occurrence. [0,0] has three zero-sum intervals, so a set is insufficient and counts matter. [1,1,2,3] has consecutive length three, so duplicates must not launch repeated run scans. In the last task, scanning boundaries from the original array instead of the distinct set can still repeat a whole run. In [4,1,2,1,2], intermediate prefix XORs need not name a singleton. Only the complete promised multiset justifies returning four. Negative values retain their 32-bit two’s-complement patterns, including the sign bit. A full-cache update of key one changes its value and recency but consumes no additional slot. A stored −1 remains OptionalInt.of(−1), whereas an absent key is OptionalInt.empty(). A miss leaves the current oldest victim unchanged.
Where the reasoning fails
Use long for target-value, prefix sums, and subarray counts. Guard Integer.MIN_VALUE before predecessor subtraction and Integer.MAX_VALUE before successor addition. HashSet iteration order is unspecified; illustrative insertion-order traces do not promise Java iteration order. Maps and sets here are not a substitute for an ordered range-query structure. Do not deduplicate before XOR, confuse XOR with exponentiation, or claim it validates arbitrary frequencies. Use a frequency map if full promise validation is required. Do not claim universal worst-case constant time for a hash-backed cache, assume HashMap iteration is recency order, or synchronize only one of the two representations. Sorted trace index cards are display copies and do not promise map iteration order.
Reconstruct the reasoning
For each of the three linked problems, write what every map/set entry means, when it is added, how duplicates behave, and why each loop’s total work has the stated bound. Then explain which representation must change if the output becomes all index pairs, a longest interval, or an online consecutive-run query. Contrast frequency counting with XOR cancellation. Explain which information each state retains and why two singletons or triple repetitions need a different derivation. Explain why a map alone, a list alone, and a map to list positions each fail to provide the desired operation costs. State the ownership and synchronization contract before proposing cache expiry or weighted capacity.