Solving Array and String Problems with Hash-Based Lookups

Good to see you again. In the previous lesson, you established a useful discipline for coding interviews: name the input size, identify the costly operation hidden inside the loop, state whether the guarantee is worst-case, expected, or amortized, and report auxiliary space separately.

Now you will apply that discipline to one of the highest-return interview patterns: hash-based lookup. The central move is simple but powerful: instead of repeatedly searching data you have already examined, preserve exactly the state needed to answer the next query quickly. In Java, that usually means choosing between HashSet and HashMap.

By the end of this lesson, you should be able to recognize the pattern, implement a correct one-pass Two Sum solution, articulate its invariant and complexity, and generalize the idea to string grouping.

---

The decision: store the answer to the next repeated question

A brute-force solution often has this shape:

1. Pick a current element.
2. Scan the remaining input to find something related to it.
3. Repeat that scan for every element.

If each scan costs $O(n)$, doing it for $n$ elements becomes $O(n^2)$. Hashing replaces that repeated scan with an expected constant-time lookup.

The design question is:

What information, if I recorded it now, would prevent me from searching again later?

That question leads to several recurring forms of hash-based state:

Problem wording or requirement	Store	Java structure
“Have I seen this value before?”	Presence of each value	HashSet<T>
“Where did I see this value?”	Value and index	HashMap<T, Integer>
“How many times has this occurred?”	Value and frequency	HashMap<T, Integer>
“Which items belong to this category?”	Canonical key and bucket	HashMap<K, List<T>>
“What state have I recorded for this identifier?”	Identifier and metadata	HashMap<K, V>

A HashSet is the right abstraction when your answer is only yes or no. A HashMap is necessary when a successful lookup must also recover information: an index, a count, a list of items, or a domain-specific state object.

For ordinary interview analysis, Java HashMap and HashSet operations such as lookup, insert, and update are expected $O(1)$. That qualifier comes directly from the normal assumption of reasonably distributed hashes, which you covered in the previous lesson.

A Java-specific contract: keys must be stable

Hash-based lookup relies on two operations for keys:

• hashCode() decides where the key is searched for.
• equals() decides whether a candidate key is actually the same key.

For this lesson’s Integer and String keys, Java handles these correctly. In production code involving custom keys, avoid mutating fields that contribute to equals() or hashCode() after insertion into a HashMap. A mutated key can become effectively unreachable even though it remains physically stored in the map.

---

Two Sum: derive the lookup rather than memorize the pattern

Consider the standard version of the problem:

Given an unsorted integer array nums and a target, return the indices of two distinct elements whose values sum to the target. Assume one valid answer exists.

For each current value $x$, the needed partner is not vague. It is determined algebraically:

$$\text{complement}=\text{target}-x$$

So, instead of asking “Which of all earlier values might pair with this?”, ask the much more precise question:

“Have I already seen target - currentValue?”

That is a hash-map lookup. Because the output requires indices, not merely whether a pair exists, the map should store each previously seen number as a key and its index as the value.

The one-pass algorithm

At every array position i:

1. Calculate the complement needed for nums[i].
2. Check whether that complement has appeared at an earlier index.
3. If it has, return its stored index and i.
4. If it has not, record the current value and index for later elements.

The ordering in steps 2 and 3 is essential: look up first, insert second.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seenIndex = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int current = nums[i];
            int complement = target - current;

            if (seenIndex.containsKey(complement)) {
                return new int[] {seenIndex.get(complement), i};
            }

            seenIndex.put(current, i);
        }

        throw new IllegalArgumentException("No valid pair exists");
    }
}

The map is not a copy of the entire input. It represents a deliberately constrained history:

Loop invariant: Just before processing index $i$, seenIndex contains a valid index for every value encountered among indices $0$ through $i-1$.

That invariant does two important things:

• It ensures a returned complement index is distinct from the current index.
• It provides the correctness argument. If a valid pair has indices $p$ and $q$, where $p<q$, then the value at $p$ has been stored by the time the loop reaches $q$. The complement lookup at $q$ succeeds.

The implementation stores only one index per numeric value. That is enough because the problem only asks for one valid pair. If the first occurrence of a value is overwritten later, the stored index still refers to a distinct element and remains valid for any future complement match.

For the image’s example, notice the subtle row for value 3 at index 2. Its complement is also 3, but 3 is not yet in the map. Only after the failed lookup do we store index 2. This is exactly why the same element cannot be used twice.

Edge cases worth stating aloud

A strong coding-interview answer handles these without adding unnecessary complexity.

• Duplicate values: nums = [3, 3], target = 6 returns [0, 1]. The first 3 is stored; the second finds it.
• Negative values: nums = [-4, 10, 7], target = 6 works unchanged because complement arithmetic and hashing work for negative integers.
• Pair appears late: the map may grow to almost $n$ entries before finding the answer.
• No answer exists: coding platforms may guarantee an answer; production-style code should define behavior, such as returning an Optional, returning an empty result, or throwing an exception.
• Integer overflow: if constraints permit values near Java’s integer limits, calculate with long or validate the input contract before using target - current.

Complexity report

Let $n$ be nums.length.

• The loop visits each array element at most once.
• Each containsKey, get, and put is expected $O(1)$.
• Therefore, runtime is expected $O(n)$.
• The map stores at most one entry per processed element, giving $O(n)$ auxiliary space.

A concise interview explanation is:

“I maintain a hash map from each previously seen value to one of its indices. For the current value, I compute the exact complement needed to reach the target and look it up before storing the current value, which guarantees distinct indices. The array is scanned once, so the solution is expected $O(n)$ time and $O(n)$ auxiliary space.”

That explanation makes the data structure, invariant, correctness property, and complexity claim explicit.

---

Generalizing to strings: canonical keys and grouping

Hashing is not only for direct membership or complement lookup. It also helps when the task asks you to group strings that are equivalent under some rule.

For example:

Group strings that are anagrams of one another.

The challenge is no longer “Have I seen this exact word?” The challenge is “How can different spellings map to the same group key?”

The answer is a canonical representation, often called a signature.

For lowercase English anagrams:

• "eat" sorts to "aet"
• "tea" sorts to "aet"
• "ate" sorts to "aet"

All and only anagrams produce the same sorted character sequence. That sorted sequence is a valid immutable String key for a hash map.

Here is the Java implementation using sorted signatures:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> groups = new HashMap<>();

        for (String word : words) {
            char[] characters = word.toCharArray();
            Arrays.sort(characters);

            String signature = new String(characters);

            groups
                .computeIfAbsent(signature, ignored -> new ArrayList<>())
                .add(word);
        }

        return new ArrayList<>(groups.values());
    }
}

The meaningful operation is not the map insertion. It is constructing the key:

1. toCharArray() copies the word’s characters.
2. Arrays.sort() creates the canonical ordering.
3. new String(characters) makes an immutable key suitable for the map.
4. computeIfAbsent creates a bucket only when that signature appears for the first time.

The result’s group ordering is unspecified because HashMap does not preserve insertion order. Usually that is acceptable because the problem states that group order and order within a group do not matter. If an API contract requires stable ordering, that must be addressed intentionally rather than assumed.

Complexity for variable-length strings

Let there be $n$ strings, and let $k$ be the maximum string length. Sorting one word costs $O(k\log k)$, so the upper-bound analysis is:

$$O(n\cdot k\log k)$$

The output itself contains all input strings arranged into groups. The map also stores a signature and list for each group, so total space is proportional to the total number of input characters and stored references:

$$O(n\cdot k)$$

More precisely, if individual string lengths vary, the sorting work is:

$$O\left(\sum _{i=1}^n{k}_i\log k_i\right)$$

This is the more accurate form to use when the prompt emphasizes highly variable word lengths.

Frequency signatures: a constraint-dependent optimization

If the problem guarantees lowercase English letters only, a 26-element frequency vector can serve as the signature. Building it takes $O(k)$ per word rather than sorting.

However, do not use a raw int[] directly as a HashMap key. Java arrays use reference identity for equals() and hashCode(), so two arrays with identical counts would not be treated as equal keys. Convert the counts to a stable value representation, such as a carefully delimited String, or wrap the array in an immutable value object with correct equals() and hashCode().

The broader lesson is more important than the particular optimization:

A hash key must encode exactly the equivalence rule of the problem, and it must be stable for the duration of its time in the map.

---

A reusable interview method for hash-based problems

Before writing code, use this short internal script:

1. State the naive repeated work.
   “For each value, scanning prior values for a match would be quadratic.”

2. Identify the precise query.
   “For this value, I need to know whether its complement has appeared.”
   Or: “For this word, I need a key representing its letter frequencies.”

3. Choose the least powerful structure that retains the needed state.
   Use a set for presence; a map for index, count, metadata, or groups.

4. State the invariant.
   “Before index $i$, the map contains data derived from earlier elements only.”
   Or: “Each map bucket contains exactly the words with that signature processed so far.”

5. Define the output and edge-case contract.
   Are you returning values, indices, counts, groups, or a boolean? What happens if no solution exists?

6. Report complexity with the hashing qualifier.
   Hash operations are expected $O(1)$; account separately for work such as sorting, copying, or building signatures.

This style is valuable in senior-level interviews because it makes the reasoning inspectable. You are not merely naming a familiar pattern; you are showing why the state representation eliminates repeated work and where its costs lie.

---

Key takeaways

• Hash-based strategies replace repeated searches with stored, queryable state.
• Choose HashSet for membership and HashMap when the lookup must return associated information such as an index, frequency, or group.
• In Two Sum, derive the complement:

$$\text{complement}=\text{target}-\text{current value}$$

• Check for the complement before storing the current value; this prevents using one array element twice.
• The one-pass Two Sum solution is expected $O(n)$ time and $O(n)$ auxiliary space.
• For string grouping, use a canonical immutable key. A sorted string is a direct anagram signature, while a frequency signature can improve performance under a constrained alphabet.
• In Java, stable equals() and hashCode() behavior is part of correct hash-map design.

Next, you will build on the same idea of maintaining only the needed state, but with a moving contiguous range: the sliding-window pattern for fixed-window and variable-window array or string problems.