Hashing and Two Pointer

Solution and explanation

Hashing

Hashing maps a key to an index in an array (bucket) using a hash function, giving O(1) average-time insert, lookup and delete. Java's HashMap and HashSet are hash tables.

key "java" → hashCode() → index 3
buckets: [ ][ ][ ][ java→5 ][ ][ python→2 ][ ]

• Collisions (two keys in one bucket) are stored in a list or, in Java 8+, a balanced tree when a bucket grows large.
• When the table fills past its load factor (0.75), it resizes and rehashes.
• Worst case degrades to O(n) with a bad hash function; average stays O(1).

Map<String, Integer> count = new HashMap<>();
for (String skill : List.of("java", "sql", "java")) count.merge(skill, 1, Integer::sum);
System.out.println(count);   // {java=2, sql=1}

Set<Integer> seen = new HashSet<>();
System.out.println(seen.add(5) + " " + seen.add(5));   // true false

Use hashing for counting frequencies, detecting duplicates, two-sum style lookups, grouping (anagrams) and caching.

Note: objects used as keys must implement equals() and hashCode() consistently.

Two pointer technique

Use two indices that move through the data according to a rule, often turning O(n²) pair checks into O(n).

• Opposite ends: on a sorted array, move left or right depending on the current sum (pair sum, container with most water, palindrome check).
• Same direction (slow/fast): remove duplicates in place, partition arrays, linked-list middle and cycle detection.

// Is there a pair with the target sum in a sorted array?
static boolean pairSum(int[] a, int target) {
    int l = 0, r = a.length - 1;
    while (l < r) {
        int s = a[l] + a[r];
        if (s == target) return true;
        if (s < target) l++; else r--;
    }
    return false;
}

Complexity

• HashMap operations: O(1) average. Two pointers: O(n) time, O(1) space (after an O(n log n) sort if needed).

Solution and explanation

Problem

Count how many times each element appears.

[10, 20, 20, 10, 10, 30] → 10:3, 20:2, 30:1

Approach 1: nested loops

For each element, count its occurrences with a second loop (skipping elements already counted). O(n²).

Approach 2: HashMap (optimal for general values)

static Map<Integer, Integer> frequency(int[] a) {
    Map<Integer, Integer> freq = new LinkedHashMap<>();   // keeps first-seen order
    for (int x : a) freq.put(x, freq.getOrDefault(x, 0) + 1);
    return freq;
}

Approach 3: counting array (small known range)

int[] count = new int[101];          // values 0..100
for (int x : a) count[x]++;

Approach 4: sort, then count runs

After sorting, equal values are adjacent; count consecutive runs. O(n log n), O(1) extra space.

Complexity

• Nested loops O(n²). HashMap O(n) time, O(k) space for k distinct values. Counting array O(n + range).

Real-world use

Counting skills across job postings, word counts, top error codes in logs.

Solution and explanation

Problem

Return indices of the two numbers that add up to a target (exactly one solution exists; you may not use the same element twice).

nums = [2, 7, 11, 15], target 9 → [0, 1]

Approach 1: check every pair

O(n²) time, O(1) space.

Approach 2: sort + two pointers

Sort (value, index) pairs and move pointers inward. O(n log n).

Approach 3: HashMap of complements (optimal)

For each number, check whether target − number has been seen; if not, store the number with its index.

static int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        Integer j = seen.get(target - nums[i]);
        if (j != null) return new int[]{j, i};
        seen.put(nums[i], i);
    }
    return new int[0];
}

Dry run

• i=0 (2): need 7, not seen; store 2→0
• i=1 (7): need 2, seen at 0 → [0, 1]

Complexity

• Pairs O(n²). Sort + pointers O(n log n). HashMap O(n) time, O(n) space.

Solution and explanation

Problem

Find the length of the longest run of consecutive integers in an unsorted array, in O(n).

[100, 4, 200, 1, 3, 2] → 4  (1, 2, 3, 4)

Approach 1: sort

Sort, then count consecutive runs (skipping duplicates). O(n log n).

Approach 2: HashSet, start only at sequence beginnings (optimal)

A number x starts a sequence only if x − 1 is not in the set; from there count upward.

static int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int x : nums) set.add(x);
    int best = 0;
    for (int x : set) {
        if (!set.contains(x - 1)) {                 // x is the start of a run
            int length = 1;
            while (set.contains(x + length)) length++;
            best = Math.max(best, length);
        }
    }
    return best;
}

Why it is O(n)

Each number is counted inside a while loop only once, as part of the run starting at its sequence beginning.

Complexity

• Sorting O(n log n). HashSet O(n) time, O(n) space.

Solution and explanation

Problem

Check whether t is an anagram of s (same letters with the same counts, any order).

"listen", "silent" → true
"rat", "car"       → false

Approach 1: sort both strings

Equal after sorting ⇔ anagrams. O(n log n).

static boolean isAnagramSort(String s, String t) {
    char[] a = s.toCharArray(), b = t.toCharArray();
    Arrays.sort(a); Arrays.sort(b);
    return Arrays.equals(a, b);
}

Approach 2: count characters (optimal)

static boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    for (int c : count) if (c != 0) return false;
    return true;
}

Complexity

• Sorting O(n log n). Counting O(n) time, O(1) space (26 letters; use a HashMap for Unicode).

Follow-up: group anagrams

Use the sorted string (or the 26-count signature) as a HashMap key to group words.

Solution and explanation

Problem

Remove duplicates in place from a sorted array so each value appears once; return the new length k (the first k elements hold the unique values).

[0, 0, 1, 1, 1, 2, 2, 3, 3, 4] → k = 5, array starts [0, 1, 2, 3, 4]

Approach 1: use a set

Copy unique values via a LinkedHashSet. O(n) time but O(n) extra space – not in place.

Approach 2: slow and fast pointers (optimal)

slow marks the end of the unique prefix; fast scans. When a new value appears, write it after slow.

static int removeDuplicates(int[] a) {
    if (a.length == 0) return 0;
    int slow = 0;
    for (int fast = 1; fast < a.length; fast++) {
        if (a[fast] != a[slow]) a[++slow] = a[fast];
    }
    return slow + 1;
}

Dry run on [1, 1, 2, 3, 3]

• fast 1 (1) same → skip
• fast 2 (2) new → a[1] = 2, slow 1
• fast 3 (3) new → a[2] = 3, slow 2
• fast 4 (3) same → k = 3, array [1, 2, 3, …]

Complexity

• Set: O(n) time, O(n) space. Two pointers: O(n) time, O(1) space.

Solution and explanation

Problem

Given wall heights, choose two walls that, with the x-axis, hold the most water. Area = min(h[i], h[j]) × (j − i).

[1, 8, 6, 2, 5, 4, 8, 3, 7] → 49 (walls 8 and 7, width 7)

Approach 1: every pair

O(n²).

Approach 2: two pointers from both ends (optimal)

Start with the widest container. The area is limited by the shorter wall, so moving the taller wall inward can never help; move the shorter one.

static int maxArea(int[] h) {
    int l = 0, r = h.length - 1, best = 0;
    while (l < r) {
        best = Math.max(best, Math.min(h[l], h[r]) * (r - l));
        if (h[l] < h[r]) l++; else r--;
    }
    return best;
}

Dry run highlights

• l=0 (1), r=8 (7): area 8 → move l
• l=1 (8), r=8 (7): area 49 → move r
• … no later area beats 49.

Complexity

• Brute force O(n²). Two pointers O(n) time, O(1) space.

Solution and explanation

Problem

Find all unique triplets that sum to zero.

[-1, 0, 1, 2, -1, -4] → [[-1, -1, 2], [-1, 0, 1]]

Approach 1: three nested loops

O(n³), plus a set to remove duplicate triplets.

Approach 2: sort + fix one + two pointers (optimal)

Sort. For each index i (skipping duplicate values), find pairs in i+1..n−1 summing to −a[i] with two pointers, skipping duplicates as you move.

static List<List<Integer>> threeSum(int[] a) {
    Arrays.sort(a);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < a.length - 2; i++) {
        if (i > 0 && a[i] == a[i - 1]) continue;          // skip duplicate first numbers
        int l = i + 1, r = a.length - 1;
        while (l < r) {
            int sum = a[i] + a[l] + a[r];
            if (sum == 0) {
                res.add(List.of(a[i], a[l], a[r]));
                while (l < r && a[l] == a[l + 1]) l++;
                while (l < r && a[r] == a[r - 1]) r--;
                l++; r--;
            } else if (sum < 0) l++;
            else r--;
        }
    }
    return res;
}

Complexity

• Brute force O(n³). Sort + two pointers O(n²) time, O(1) extra space (besides output).

Note: if the smallest number a[i] is already > 0, you can stop early.