A hash set or hash map answers “have I seen this value?” in O(1) on average. Almost every problem in this topic is an O(n²) double loop that collapses to O(n) once the inner loop is replaced by one hash lookup — and half of them use the same trick: prefix sums stored in a hash map.

The containers you will reach for

Need	Python	C++	Java	JavaScript
membership only	`set`	`unordered_set`	`HashSet`	`Set`
key → value / count	`dict`, `Counter`	`unordered_map`	`HashMap`	`Map`
insert / lookup / erase	`O(1)` avg	`O(1)` avg	`O(1)` avg	`O(1)` avg
iteration order	insertion order	unspecified	unspecified	insertion order

Two questions decide the whole design of a hashing solution:

The prefix-sum + hash map pattern

Let prefix[j] = arr[0] + … + arr[j]. Then the sum of any subarray is a difference of two prefix sums:

sum(arr[i..j]) = prefix[j] − prefix[i−1]

So “is there a subarray ending at j with sum S?” becomes “did the value prefix[j] − S appear as an earlier prefix sum?” — a single hash lookup instead of an inner loop over every start i.

Two equal prefix sums ⇒ the elements between them sum to 0

index   :   0    1    2    3    4    5    6
arr     : [ 5,   8,  -4,  -4,   9,  -2,   2 ]
prefix  : [ 5,  13,   9,   5,  14,  12,  14 ]
            ↑              ↑
       prefix[0] = 5  prefix[3] = 5   →  arr[1..3] = 8 − 4 − 4 = 0   (length 3 − 0 = 3)

Seed the map with prefix = 0 at index −1
The empty prefix. It makes a subarray that starts at index 0 fall out of the same formula instead of needing a special case.
Walk left to right, updating prefix
One addition per element.
Look up prefix − S
Found at index k ⇒ arr[k+1..j] sums to S. For existence answer immediately; for longest take j − k; for count add the stored count.
Insert prefix only if it is new
Keeping the first index gives the longest subarray; a later duplicate would only shorten it.

Intersection of two unsorted arrays

Count the distinct values that appear in both arrays. Duplicates inside one array (the two 20s, the two 30s) are counted once.

Naive: for each element of a, skip it if it already appeared earlier in a, otherwise scan b for it. Two nested scans per element.

Python — naive

def intersection_count(a, b):
    res = 0
    for i in range(len(a)):
        seen_before = False
        for j in range(i):              # did a[i] already appear in a[0..i-1]?
            if a[j] == a[i]:
                seen_before = True
                break
        if seen_before:
            continue
        for y in b:                     # is a[i] present in b?
            if y == a[i]:
                res += 1
                break
    return res

print(intersection_count([10, 15, 20, 5, 20], [30, 5, 30, 80]))
print(intersection_count([1, 2, 3, 2, 4, 5], [3, 4, 5, 6]))

Output

1
3

Time O(m · (m + n)) · Space O(1)

Python

def intersection_count(a, b):
    remaining = set(a)             # distinct elements of a
    count = 0
    for x in b:
        if x in remaining:         # common value — count it once …
            count += 1
            remaining.remove(x)    # … by removing it immediately
    return count

print(intersection_count([10, 15, 20, 5, 20], [30, 5, 30, 80]))
print(intersection_count([1, 2, 3, 2, 4, 5], [3, 4, 5, 6]))

C++

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int intersectionCount(const vector<int>& a, const vector<int>& b) {
    unordered_set<int> remaining(a.begin(), a.end());   // distinct elements of a
    int count = 0;
    for (int x : b) {
        if (remaining.count(x)) {      // common value — count it once …
            count++;
            remaining.erase(x);        // … by removing it immediately
        }
    }
    return count;
}

int main() {
    cout << intersectionCount({10, 15, 20, 5, 20}, {30, 5, 30, 80}) << "\n";
    cout << intersectionCount({1, 2, 3, 2, 4, 5}, {3, 4, 5, 6}) << "\n";
}

Java

import java.util.HashSet;
import java.util.Set;

public class Main {
    static int intersectionCount(int[] a, int[] b) {
        Set<Integer> remaining = new HashSet<>();     // distinct elements of a
        for (int x : a) remaining.add(x);
        int count = 0;
        for (int x : b) {
            if (remaining.remove(x)) count++;        // remove() is true only if x was present
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(intersectionCount(new int[]{10, 15, 20, 5, 20}, new int[]{30, 5, 30, 80}));
        System.out.println(intersectionCount(new int[]{1, 2, 3, 2, 4, 5}, new int[]{3, 4, 5, 6}));
    }
}

JavaScript

function intersectionCount(a, b) {
    const remaining = new Set(a);          // distinct elements of a
    let count = 0;
    for (const x of b) {
        if (remaining.delete(x)) count++;  // delete() is true only if x was present
    }
    return count;
}

console.log(intersectionCount([10, 15, 20, 5, 20], [30, 5, 30, 80]));
console.log(intersectionCount([1, 2, 3, 2, 4, 5], [3, 4, 5, 6]));

Output

1
3

Time O(m + n) · Space O(m)

Union of two unsorted arrays

Count the distinct values present in at least one of the arrays. The naive way copies both into one array of m + n elements and, for each element, scans everything before it to see whether it is a repeat.

Python — naive

def union_count(a, b):
    c = a + b                        # all m + n elements
    res = 0
    for i in range(len(c)):
        repeat = False
        for j in range(i):           # did c[i] already appear?
            if c[j] == c[i]:
                repeat = True
                break
        if not repeat:
            res += 1
    return res

print(union_count([15, 20, 5, 15], [15, 15, 15, 20, 10]))
print(union_count([1, 2, 3, 2, 4, 5], [3, 4, 5, 6]))

Output

4
6

Time O((m + n)²) · Space O(m + n)

Python

def union_count(a, b):
    s = set()
    for x in a:
        s.add(x)          # duplicates are silently ignored
    for x in b:
        s.add(x)
    return len(s)

print(union_count([15, 20, 5, 15], [15, 15, 15, 20, 10]))
print(union_count([1, 2, 3, 2, 4, 5], [3, 4, 5, 6]))

C++

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int unionCount(const vector<int>& a, const vector<int>& b) {
    unordered_set<int> s;
    for (int x : a) s.insert(x);      // duplicates are silently ignored
    for (int x : b) s.insert(x);
    return (int)s.size();
}

int main() {
    cout << unionCount({15, 20, 5, 15}, {15, 15, 15, 20, 10}) << "\n";
    cout << unionCount({1, 2, 3, 2, 4, 5}, {3, 4, 5, 6}) << "\n";
}

Java

import java.util.HashSet;
import java.util.Set;

public class Main {
    static int unionCount(int[] a, int[] b) {
        Set<Integer> s = new HashSet<>();
        for (int x : a) s.add(x);        // duplicates are silently ignored
        for (int x : b) s.add(x);
        return s.size();
    }

    public static void main(String[] args) {
        System.out.println(unionCount(new int[]{15, 20, 5, 15}, new int[]{15, 15, 15, 20, 10}));
        System.out.println(unionCount(new int[]{1, 2, 3, 2, 4, 5}, new int[]{3, 4, 5, 6}));
    }
}

JavaScript

function unionCount(a, b) {
    const s = new Set();
    for (const x of a) s.add(x);         // duplicates are silently ignored
    for (const x of b) s.add(x);
    return s.size;
}

console.log(unionCount([15, 20, 5, 15], [15, 15, 15, 20, 10]));
console.log(unionCount([1, 2, 3, 2, 4, 5], [3, 4, 5, 6]));

Output

4
6

Time O(m + n) · Space O(m + n)

Pair with given sum

Does the array contain two different elements whose sum is x? The naive check tries every pair.

Python — naive

def has_pair(arr, x):
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] + arr[j] == x:
                return True
    return False

print("Yes" if has_pair([3, 2, 8, 15, -18], 17) else "No")
print("Yes" if has_pair([2, 1, 6, 3], 6) else "No")

Output

Yes
No

Time O(n²) · Space O(1)

Python

def has_pair(arr, x):
    seen = set()
    for v in arr:
        if x - v in seen:       # complement met earlier → pair found
            return True
        seen.add(v)             # insert AFTER the check
    return False

for arr, x in [([3, 2, 8, 15, -18], 17), ([2, 1, 6, 3], 6), ([3], 6)]:
    print("sum =", x, "→", "Yes" if has_pair(arr, x) else "No")

C++

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

bool hasPair(const vector<int>& arr, int x) {
    unordered_set<int> seen;
    for (int v : arr) {
        if (seen.count(x - v)) return true;   // complement met earlier → pair found
        seen.insert(v);                       // insert AFTER the check
    }
    return false;
}

int main() {
    vector<pair<vector<int>, int>> tests = {{{3, 2, 8, 15, -18}, 17}, {{2, 1, 6, 3}, 6}, {{3}, 6}};
    for (auto& [arr, x] : tests)
        cout << "sum = " << x << " → " << (hasPair(arr, x) ? "Yes" : "No") << "\n";
}

Java

import java.util.HashSet;
import java.util.Set;

public class Main {
    static boolean hasPair(int[] arr, int x) {
        Set<Integer> seen = new HashSet<>();
        for (int v : arr) {
            if (seen.contains(x - v)) return true;   // complement met earlier → pair found
            seen.add(v);                             // insert AFTER the check
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] arrays = {{3, 2, 8, 15, -18}, {2, 1, 6, 3}, {3}};
        int[] sums = {17, 6, 6};
        for (int t = 0; t < arrays.length; t++)
            System.out.println("sum = " + sums[t] + " → " + (hasPair(arrays[t], sums[t]) ? "Yes" : "No"));
    }
}

JavaScript

function hasPair(arr, x) {
    const seen = new Set();
    for (const v of arr) {
        if (seen.has(x - v)) return true;   // complement met earlier → pair found
        seen.add(v);                        // insert AFTER the check
    }
    return false;
}

for (const [arr, x] of [[[3, 2, 8, 15, -18], 17], [[2, 1, 6, 3], 6], [[3], 6]])
    console.log("sum =", x, "→", hasPair(arr, x) ? "Yes" : "No");

Output

sum = 17 → Yes
sum = 6 → No
sum = 6 → No

Time O(n) · Space O(n)

Subarray with 0 sum

Is there a contiguous subarray whose elements sum to zero? The naive solution computes the sum of every (i, j) range.

Python — naive

def has_zero_sum(arr):
    n = len(arr)
    for i in range(n):
        s = 0
        for j in range(i, n):      # extend the subarray one element at a time
            s += arr[j]
            if s == 0:
                return True
    return False

print("Yes" if has_zero_sum([1, 2, 3, 2, 4, 5]) else "No")
print("Yes" if has_zero_sum([-1, 4, -3, 5, 1]) else "No")

Output

No
Yes

Time O(n²) · Space O(1)

Prefix sums of the second example

arr    : [ -1,  4, -3,  5,  1 ]
prefix : [ -1,  3,  0,  5,  6 ]
                     ↑
               prefix[2] = 0  →  arr[0..2] sums to 0  →  Yes

Python

def has_zero_sum(arr):
    seen = {0}            # the empty prefix: lets a subarray start at index 0
    prefix = 0
    for v in arr:
        prefix += v
        if prefix in seen:    # same prefix twice → the gap sums to 0
            return True
        seen.add(prefix)
    return False

for arr in [[1, 2, 3, 2, 4, 5], [-1, 4, -3, 5, 1], [4, -3, -1, 2]]:
    print("Yes" if has_zero_sum(arr) else "No")

C++

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

bool hasZeroSum(const vector<int>& arr) {
    unordered_set<int> seen = {0};     // the empty prefix: lets a subarray start at index 0
    int prefix = 0;
    for (int v : arr) {
        prefix += v;
        if (seen.count(prefix)) return true;   // same prefix twice → the gap sums to 0
        seen.insert(prefix);
    }
    return false;
}

int main() {
    vector<vector<int>> tests = {{1, 2, 3, 2, 4, 5}, {-1, 4, -3, 5, 1}, {4, -3, -1, 2}};
    for (auto& arr : tests) cout << (hasZeroSum(arr) ? "Yes" : "No") << "\n";
}

Java

import java.util.HashSet;
import java.util.Set;

public class Main {
    static boolean hasZeroSum(int[] arr) {
        Set<Integer> seen = new HashSet<>();
        seen.add(0);                       // the empty prefix: lets a subarray start at index 0
        int prefix = 0;
        for (int v : arr) {
            prefix += v;
            if (!seen.add(prefix)) return true;   // add() is false when prefix was already there
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] tests = {{1, 2, 3, 2, 4, 5}, {-1, 4, -3, 5, 1}, {4, -3, -1, 2}};
        for (int[] arr : tests) System.out.println(hasZeroSum(arr) ? "Yes" : "No");
    }
}

JavaScript

function hasZeroSum(arr) {
    const seen = new Set([0]);      // the empty prefix: lets a subarray start at index 0
    let prefix = 0;
    for (const v of arr) {
        prefix += v;
        if (seen.has(prefix)) return true;   // same prefix twice → the gap sums to 0
        seen.add(prefix);
    }
    return false;
}

for (const arr of [[1, 2, 3, 2, 4, 5], [-1, 4, -3, 5, 1], [4, -3, -1, 2]])
    console.log(hasZeroSum(arr) ? "Yes" : "No");

Output

No
Yes
Yes

Time O(n) · Space O(n)

Check for palindrome permutation

Can the characters of s be rearranged into a palindrome? Generating every permutation and testing each one is hopeless beyond a handful of characters — n! candidates.

Python — naive

from itertools import permutations

def can_be_palindrome(s):
    for perm in permutations(s):           # n! permutations
        t = ''.join(perm)
        if t == t[::-1]:
            return True
    return False

print("Yes" if can_be_palindrome("geek") else "No")
print("Yes" if can_be_palindrome("geegg") else "No")

Output

No
Yes

Time O(n! · n) · Space O(n)

Python

def can_be_palindrome(s):
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
    odd = 0
    for count in freq.values():
        if count % 2 == 1:
            odd += 1
            if odd > 1:          # two characters without a partner
                return False
    return True

for s in ["geek", "geegg", "aab", "abc"]:
    print(s, "→", "Yes" if can_be_palindrome(s) else "No")

C++

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

bool canBePalindrome(const string& s) {
    unordered_map<char, int> freq;
    for (char ch : s) freq[ch]++;
    int odd = 0;
    for (auto& [ch, count] : freq) {
        if (count % 2 == 1 && ++odd > 1) return false;   // two characters without a partner
    }
    return true;
}

int main() {
    for (string s : {"geek", "geegg", "aab", "abc"})
        cout << s << " → " << (canBePalindrome(s) ? "Yes" : "No") << "\n";
}

Java

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

public class Main {
    static boolean canBePalindrome(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char ch : s.toCharArray()) freq.merge(ch, 1, Integer::sum);
        int odd = 0;
        for (int count : freq.values()) {
            if (count % 2 == 1 && ++odd > 1) return false;   // two characters without a partner
        }
        return true;
    }

    public static void main(String[] args) {
        for (String s : new String[]{"geek", "geegg", "aab", "abc"})
            System.out.println(s + " → " + (canBePalindrome(s) ? "Yes" : "No"));
    }
}

JavaScript

function canBePalindrome(s) {
    const freq = new Map();
    for (const ch of s) freq.set(ch, (freq.get(ch) ?? 0) + 1);
    let odd = 0;
    for (const count of freq.values()) {
        if (count % 2 === 1 && ++odd > 1) return false;   // two characters without a partner
    }
    return true;
}

for (const s of ["geek", "geegg", "aab", "abc"])
    console.log(s, "→", canBePalindrome(s) ? "Yes" : "No");

Output

geek → No
geegg → Yes
aab → Yes
abc → No

Time O(n) · Space O(k) for k distinct characters

Longest subarray with given sum

Return the length of the longest contiguous subarray whose sum is exactly S (0 if none). Naive: start at every i, extend to every j, keep the longest hit.

Python — naive

def longest_with_sum(arr, S):
    n, res = len(arr), 0
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += arr[j]
            if s == S:
                res = max(res, j - i + 1)
    return res

print(longest_with_sum([5, 8, -4, -4, 9, -2, 2], 0))
print(longest_with_sum([3, 1, 0, 1, 8, 2, 3, 6], 5))

Output

3
4

Time O(n²) · Space O(1)

Python

def longest_with_sum(arr, S):
    first = {0: -1}            # prefix sum → first index where it occurred
    prefix = 0
    best = 0
    for j, v in enumerate(arr):
        prefix += v
        if prefix - S in first:                 # subarray (first[prefix-S], j] sums to S
            best = max(best, j - first[prefix - S])
        if prefix not in first:                 # keep the FIRST occurrence only
            first[prefix] = j
    return best

print(longest_with_sum([5, 8, -4, -4, 9, -2, 2], 0))
print(longest_with_sum([3, 1, 0, 1, 8, 2, 3, 6], 5))
print(longest_with_sum([8, 3, 7], 15))

C++

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int longestWithSum(const vector<int>& arr, int S) {
    unordered_map<int, int> first = {{0, -1}};   // prefix sum → first index where it occurred
    int prefix = 0, best = 0;
    int n = arr.size();
    for (int j = 0; j < n; j++) {
        prefix += arr[j];
        auto it = first.find(prefix - S);
        if (it != first.end()) best = max(best, j - it->second);   // subarray (it->second, j] sums to S
        first.try_emplace(prefix, j);            // inserts only if absent → keeps the FIRST occurrence
    }
    return best;
}

int main() {
    cout << longestWithSum({5, 8, -4, -4, 9, -2, 2}, 0) << "\n";
    cout << longestWithSum({3, 1, 0, 1, 8, 2, 3, 6}, 5) << "\n";
    cout << longestWithSum({8, 3, 7}, 15) << "\n";
}

Java

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

public class Main {
    static int longestWithSum(int[] arr, int S) {
        Map<Integer, Integer> first = new HashMap<>();   // prefix sum → first index where it occurred
        first.put(0, -1);
        int prefix = 0, best = 0;
        for (int j = 0; j < arr.length; j++) {
            prefix += arr[j];
            Integer k = first.get(prefix - S);
            if (k != null) best = Math.max(best, j - k);   // subarray (k, j] sums to S
            first.putIfAbsent(prefix, j);                  // keeps the FIRST occurrence
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(longestWithSum(new int[]{5, 8, -4, -4, 9, -2, 2}, 0));
        System.out.println(longestWithSum(new int[]{3, 1, 0, 1, 8, 2, 3, 6}, 5));
        System.out.println(longestWithSum(new int[]{8, 3, 7}, 15));
    }
}

JavaScript

function longestWithSum(arr, S) {
    const first = new Map([[0, -1]]);     // prefix sum → first index where it occurred
    let prefix = 0, best = 0;
    for (let j = 0; j < arr.length; j++) {
        prefix += arr[j];
        if (first.has(prefix - S)) best = Math.max(best, j - first.get(prefix - S));  // (k, j] sums to S
        if (!first.has(prefix)) first.set(prefix, j);   // keeps the FIRST occurrence
    }
    return best;
}

console.log(longestWithSum([5, 8, -4, -4, 9, -2, 2], 0));
console.log(longestWithSum([3, 1, 0, 1, 8, 2, 3, 6], 5));
console.log(longestWithSum([8, 3, 7], 15));

Output

3
4
0

Time O(n) · Space O(n)

Longest subarray with equal 0s and 1s

In a binary array, find the longest contiguous subarray with as many 0s as 1s. The naive version tracks a running +1 / −1 score from each start.

Python — naive

def longest_equal(arr):
    n, best, start = len(arr), 0, -1
    for i in range(n):
        score = 0
        for j in range(i, n):
            score += 1 if arr[j] == 1 else -1
            if score == 0 and j - i + 1 > best:
                best, start = j - i + 1, i
    if best:
        print("indices", start, "to", start + best - 1)
    return best

print(longest_equal([1, 0, 0, 1, 0, 1, 1]))

Output

indices 0 to 5
6

Time O(n²) · Space O(1)

Python

def longest_equal(arr):
    first = {0: -1}
    prefix = 0
    best = 0
    for j, bit in enumerate(arr):
        prefix += 1 if bit == 1 else -1      # 0 counts as -1 (the input is not modified)
        if prefix in first:
            best = max(best, j - first[prefix])
        else:
            first[prefix] = j
    return best

for arr in [[1, 0, 0, 1, 0, 1, 1], [1, 1, 1, 0], [0, 0, 1, 1, 0]]:
    print(longest_equal(arr))

C++

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int longestEqual(const vector<int>& arr) {
    unordered_map<int, int> first = {{0, -1}};
    int prefix = 0, best = 0;
    int n = arr.size();
    for (int j = 0; j < n; j++) {
        prefix += arr[j] == 1 ? 1 : -1;        // 0 counts as -1 (the input is not modified)
        auto it = first.find(prefix);
        if (it != first.end()) best = max(best, j - it->second);
        else first[prefix] = j;
    }
    return best;
}

int main() {
    vector<vector<int>> tests = {{1, 0, 0, 1, 0, 1, 1}, {1, 1, 1, 0}, {0, 0, 1, 1, 0}};
    for (auto& arr : tests) cout << longestEqual(arr) << "\n";
}

Java

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

public class Main {
    static int longestEqual(int[] arr) {
        Map<Integer, Integer> first = new HashMap<>();
        first.put(0, -1);
        int prefix = 0, best = 0;
        for (int j = 0; j < arr.length; j++) {
            prefix += arr[j] == 1 ? 1 : -1;    // 0 counts as -1 (the input is not modified)
            Integer k = first.get(prefix);
            if (k != null) best = Math.max(best, j - k);
            else first.put(prefix, j);
        }
        return best;
    }

    public static void main(String[] args) {
        int[][] tests = {{1, 0, 0, 1, 0, 1, 1}, {1, 1, 1, 0}, {0, 0, 1, 1, 0}};
        for (int[] arr : tests) System.out.println(longestEqual(arr));
    }
}

JavaScript

function longestEqual(arr) {
    const first = new Map([[0, -1]]);
    let prefix = 0, best = 0;
    for (let j = 0; j < arr.length; j++) {
        prefix += arr[j] === 1 ? 1 : -1;       // 0 counts as -1 (the input is not modified)
        if (first.has(prefix)) best = Math.max(best, j - first.get(prefix));
        else first.set(prefix, j);
    }
    return best;
}

for (const arr of [[1, 0, 0, 1, 0, 1, 1], [1, 1, 1, 0], [0, 0, 1, 1, 0]])
    console.log(longestEqual(arr));

Output

6
2
4

Time O(n) · Space O(n)

Longest common span with same sum in two binary arrays

Two binary arrays of the same length. Find the longest index range [i..j] such that a[i..j] and b[i..j] have the same sum. Naive: for every start, extend both running sums together.

Python — naive

def longest_common_span(a, b):
    n, res = len(a), 0
    for i in range(n):
        sum_a = sum_b = 0
        for j in range(i, n):
            sum_a += a[j]
            sum_b += b[j]
            if sum_a == sum_b:
                res = max(res, j - i + 1)
    return res

print(longest_common_span([0, 1, 0, 0, 0, 0], [1, 0, 1, 0, 0, 1]))
print(longest_common_span([0, 0, 0], [1, 1, 1]))

Output

4
0

Time O(n²) · Space O(1)

Equal prefix sums of a − b at indices 0 and 4 ⇒ a[1..4] and b[1..4] have equal sums

a      : [ 0,  1,  0,  0,  0,  0 ]
b      : [ 1,  0,  1,  0,  0,  1 ]
a − b  : [-1,  1, -1,  0,  0, -1 ]
prefix : [-1,  0, -1, -1, -1, -2 ]
           ↑               ↑
     first(-1) = 0      j = 4   →  length 4 − 0 = 4

Python

def longest_common_span(a, b):
    first = {0: -1}
    prefix = 0
    best = 0
    for j in range(len(a)):
        prefix += a[j] - b[j]         # prefix sum of the difference array
        if prefix in first:
            best = max(best, j - first[prefix])
        else:
            first[prefix] = j
    return best

print(longest_common_span([0, 1, 0, 0, 0, 0], [1, 0, 1, 0, 0, 1]))
print(longest_common_span([0, 0, 0], [1, 1, 1]))
print(longest_common_span([0, 0, 1, 0], [1, 1, 1, 1]))

C++

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int longestCommonSpan(const vector<int>& a, const vector<int>& b) {
    unordered_map<int, int> first = {{0, -1}};
    int prefix = 0, best = 0;
    int n = a.size();
    for (int j = 0; j < n; j++) {
        prefix += a[j] - b[j];               // prefix sum of the difference array
        auto it = first.find(prefix);
        if (it != first.end()) best = max(best, j - it->second);
        else first[prefix] = j;
    }
    return best;
}

int main() {
    cout << longestCommonSpan({0, 1, 0, 0, 0, 0}, {1, 0, 1, 0, 0, 1}) << "\n";
    cout << longestCommonSpan({0, 0, 0}, {1, 1, 1}) << "\n";
    cout << longestCommonSpan({0, 0, 1, 0}, {1, 1, 1, 1}) << "\n";
}

Java

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

public class Main {
    static int longestCommonSpan(int[] a, int[] b) {
        Map<Integer, Integer> first = new HashMap<>();
        first.put(0, -1);
        int prefix = 0, best = 0;
        for (int j = 0; j < a.length; j++) {
            prefix += a[j] - b[j];           // prefix sum of the difference array
            Integer k = first.get(prefix);
            if (k != null) best = Math.max(best, j - k);
            else first.put(prefix, j);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSpan(new int[]{0, 1, 0, 0, 0, 0}, new int[]{1, 0, 1, 0, 0, 1}));
        System.out.println(longestCommonSpan(new int[]{0, 0, 0}, new int[]{1, 1, 1}));
        System.out.println(longestCommonSpan(new int[]{0, 0, 1, 0}, new int[]{1, 1, 1, 1}));
    }
}

JavaScript

function longestCommonSpan(a, b) {
    const first = new Map([[0, -1]]);
    let prefix = 0, best = 0;
    for (let j = 0; j < a.length; j++) {
        prefix += a[j] - b[j];               // prefix sum of the difference array
        if (first.has(prefix)) best = Math.max(best, j - first.get(prefix));
        else first.set(prefix, j);
    }
    return best;
}

console.log(longestCommonSpan([0, 1, 0, 0, 0, 0], [1, 0, 1, 0, 0, 1]));
console.log(longestCommonSpan([0, 0, 0], [1, 1, 1]));
console.log(longestCommonSpan([0, 0, 1, 0], [1, 1, 1, 1]));

Output

4
0
1

Time O(n) · Space O(n)

Longest consecutive subsequence

Find the length of the longest run of consecutive integers x, x+1, x+2, … whose members all appear in the array — in any order and possibly with duplicates. Sorting makes runs adjacent, which gives an O(n log n) solution.

Python — sorting

def longest_consecutive(arr):
    arr = sorted(arr)
    best = run = 1
    for i in range(1, len(arr)):
        if arr[i] == arr[i - 1]:          # duplicate: neither extends nor breaks the run
            continue
        if arr[i] == arr[i - 1] + 1:
            run += 1
        else:
            best = max(best, run)
            run = 1
    return max(best, run)

print(longest_consecutive([1, 9, 3, 4, 2, 20]))
print(longest_consecutive([1, 2, 2, 3]))      # the original notes' version returned 2 here

Output

4
3

Time O(n log n) · Space O(n) for the sorted copy

Python

def longest_consecutive(arr):
    s = set(arr)
    best = 0
    for x in s:                      # iterate the set: duplicates handled for free
        if x - 1 in s:
            continue                 # not the start of a run
        run = 1
        while x + run in s:          # walk the run upward
            run += 1
        best = max(best, run)
    return best

for arr in [[1, 9, 3, 4, 2, 20], [8, 20, 7, 30], [20, 30, 40]]:
    print(longest_consecutive(arr))

C++

#include <algorithm>
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int longestConsecutive(const vector<int>& arr) {
    unordered_set<int> s(arr.begin(), arr.end());
    int best = 0;
    for (int x : s) {                       // iterate the set: duplicates handled for free
        if (s.count(x - 1)) continue;       // not the start of a run
        int run = 1;
        while (s.count(x + run)) run++;     // walk the run upward
        best = max(best, run);
    }
    return best;
}

int main() {
    vector<vector<int>> tests = {{1, 9, 3, 4, 2, 20}, {8, 20, 7, 30}, {20, 30, 40}};
    for (auto& arr : tests) cout << longestConsecutive(arr) << "\n";
}

Java

import java.util.HashSet;
import java.util.Set;

public class Main {
    static int longestConsecutive(int[] arr) {
        Set<Integer> s = new HashSet<>();
        for (int x : arr) s.add(x);
        int best = 0;
        for (int x : s) {                            // iterate the set: duplicates handled for free
            if (s.contains(x - 1)) continue;         // not the start of a run
            int run = 1;
            while (s.contains(x + run)) run++;       // walk the run upward
            best = Math.max(best, run);
        }
        return best;
    }

    public static void main(String[] args) {
        int[][] tests = {{1, 9, 3, 4, 2, 20}, {8, 20, 7, 30}, {20, 30, 40}};
        for (int[] arr : tests) System.out.println(longestConsecutive(arr));
    }
}

JavaScript

function longestConsecutive(arr) {
    const s = new Set(arr);
    let best = 0;
    for (const x of s) {                     // iterate the set: duplicates handled for free
        if (s.has(x - 1)) continue;          // not the start of a run
        let run = 1;
        while (s.has(x + run)) run++;        // walk the run upward
        best = Math.max(best, run);
    }
    return best;
}

for (const arr of [[1, 9, 3, 4, 2, 20], [8, 20, 7, 30], [20, 30, 40]])
    console.log(longestConsecutive(arr));

Output

4
2
1

Time O(n) · Space O(n)

Count distinct elements in every window

For each of the n − k + 1 windows of size k, print the number of distinct values in it. The naive solution rebuilds a set for every window.

Python — naive

def distinct_in_windows(arr, k):
    n = len(arr)
    return [len(set(arr[i:i + k])) for i in range(n - k + 1)]   # n-k+1 windows, O(k) each

print(*distinct_in_windows([10, 20, 20, 10, 30, 40, 10], 4))
print(*distinct_in_windows([10, 20, 30, 40], 3))

Output

2 3 4 3
3 3

Time O(n · k) · Space O(k)

Each slide changes two counts; the map size is the answer

arr = [10, 20, 20, 10, 30, 40, 10],  k = 4

window [10 20 20 10]   counts {10:2, 20:2}            → 2
slide:  −10  +30       counts {10:1, 20:2, 30:1}      → 3
slide:  −20  +40       counts {10:1, 20:1, 30:1, 40:1}→ 4
slide:  −20  +10       counts {10:2, 30:1, 40:1}      → 3   (20 dropped to 0 → key removed)

Python

def distinct_in_windows(arr, k):
    count = {}
    for x in arr[:k]:                      # first window
        count[x] = count.get(x, 0) + 1
    res = [len(count)]
    for i in range(k, len(arr)):
        out, inc = arr[i - k], arr[i]
        count[out] -= 1
        if count[out] == 0:
            del count[out]                 # a key with count 0 must not stay in the map
        count[inc] = count.get(inc, 0) + 1
        res.append(len(count))
    return res

print(" ".join(map(str, distinct_in_windows([10, 20, 20, 10, 30, 40, 10], 4))))
print(" ".join(map(str, distinct_in_windows([10, 20, 30, 40], 3))))

C++

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

vector<int> distinctInWindows(const vector<int>& arr, int k) {
    unordered_map<int, int> count;
    int n = arr.size();
    for (int i = 0; i < k; i++) count[arr[i]]++;        // first window
    vector<int> res = {(int)count.size()};
    for (int i = k; i < n; i++) {
        int out = arr[i - k];
        if (--count[out] == 0) count.erase(out);        // a key with count 0 must not stay in the map
        count[arr[i]]++;
        res.push_back((int)count.size());
    }
    return res;
}

void print(const vector<int>& v) {
    for (size_t i = 0; i < v.size(); i++) cout << (i ? " " : "") << v[i];
    cout << "\n";
}

int main() {
    print(distinctInWindows({10, 20, 20, 10, 30, 40, 10}, 4));
    print(distinctInWindows({10, 20, 30, 40}, 3));
}

Java

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

public class Main {
    static List<Integer> distinctInWindows(int[] arr, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int i = 0; i < k; i++) count.merge(arr[i], 1, Integer::sum);   // first window
        List<Integer> res = new ArrayList<>();
        res.add(count.size());
        for (int i = k; i < arr.length; i++) {
            int out = arr[i - k];
            if (count.merge(out, -1, Integer::sum) == 0) count.remove(out);  // count 0 → remove the key
            count.merge(arr[i], 1, Integer::sum);
            res.add(count.size());
        }
        return res;
    }

    static void print(List<Integer> v) {
        StringBuilder sb = new StringBuilder();
        for (int x : v) sb.append(sb.length() == 0 ? "" : " ").append(x);
        System.out.println(sb);
    }

    public static void main(String[] args) {
        print(distinctInWindows(new int[]{10, 20, 20, 10, 30, 40, 10}, 4));
        print(distinctInWindows(new int[]{10, 20, 30, 40}, 3));
    }
}

JavaScript

function distinctInWindows(arr, k) {
    const count = new Map();
    for (let i = 0; i < k; i++) count.set(arr[i], (count.get(arr[i]) ?? 0) + 1);   // first window
    const res = [count.size];
    for (let i = k; i < arr.length; i++) {
        const out = arr[i - k];
        if (count.get(out) === 1) count.delete(out);        // a key with count 0 must not stay in the map
        else count.set(out, count.get(out) - 1);
        count.set(arr[i], (count.get(arr[i]) ?? 0) + 1);
        res.push(count.size);
    }
    return res;
}

console.log(distinctInWindows([10, 20, 20, 10, 30, 40, 10], 4).join(" "));
console.log(distinctInWindows([10, 20, 30, 40], 3).join(" "));

Output

2 3 4 3
3 3

Time O(n) · Space O(k)

Elements appearing more than n/k times

Print every value that occurs strictly more than n / k times (n / k with integer division). k = 2 is the classic majority element. Sorting groups equal values together, so a single pass can count runs:

Python — sorting

def more_than_n_by_k(arr, k):
    arr = sorted(arr)
    n = len(arr)
    res = []
    i = 0
    while i < n:
        j = i
        while j < n and arr[j] == arr[i]:   # end of this run of equal values
            j += 1
        if j - i > n // k:
            res.append(arr[i])
        i = j
    return res

print(*more_than_n_by_k([30, 10, 20, 20, 10, 20, 30, 30], 4))
print(*more_than_n_by_k([2, 2, 1, 2, 3, 2], 2))

Output

20 30
2

Time O(n log n) · Space O(1) extra (in-place sort)

Python

def more_than_n_by_k(arr, k):
    n = len(arr)
    count = {}
    for x in arr:
        count[x] = count.get(x, 0) + 1
    return sorted(x for x, c in count.items() if c > n // k)   # sort: map order is not portable

print(" ".join(map(str, more_than_n_by_k([30, 10, 20, 20, 10, 20, 30, 30], 4))))
print(" ".join(map(str, more_than_n_by_k([2, 2, 1, 2, 3, 2], 2))))

C++

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

vector<int> moreThanNByK(const vector<int>& arr, int k) {
    int n = arr.size();
    unordered_map<int, int> count;
    for (int x : arr) count[x]++;
    vector<int> res;
    for (auto& [x, c] : count)
        if (c > n / k) res.push_back(x);
    sort(res.begin(), res.end());          // sort: map order is not portable
    return res;
}

void print(const vector<int>& v) {
    for (size_t i = 0; i < v.size(); i++) cout << (i ? " " : "") << v[i];
    cout << "\n";
}

int main() {
    print(moreThanNByK({30, 10, 20, 20, 10, 20, 30, 30}, 4));
    print(moreThanNByK({2, 2, 1, 2, 3, 2}, 2));
}

Java

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

public class Main {
    static List<Integer> moreThanNByK(int[] arr, int k) {
        int n = arr.length;
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : arr) count.merge(x, 1, Integer::sum);
        List<Integer> res = new ArrayList<>();
        for (Map.Entry<Integer, Integer> e : count.entrySet())
            if (e.getValue() > n / k) res.add(e.getKey());
        Collections.sort(res);                 // sort: map order is not portable
        return res;
    }

    static void print(List<Integer> v) {
        StringBuilder sb = new StringBuilder();
        for (int x : v) sb.append(sb.length() == 0 ? "" : " ").append(x);
        System.out.println(sb);
    }

    public static void main(String[] args) {
        print(moreThanNByK(new int[]{30, 10, 20, 20, 10, 20, 30, 30}, 4));
        print(moreThanNByK(new int[]{2, 2, 1, 2, 3, 2}, 2));
    }
}

JavaScript

function moreThanNByK(arr, k) {
    const n = arr.length;
    const count = new Map();
    for (const x of arr) count.set(x, (count.get(x) ?? 0) + 1);
    const res = [];
    for (const [x, c] of count)
        if (c > Math.floor(n / k)) res.push(x);
    return res.sort((a, b) => a - b);          // sort: map order is not portable
}

console.log(moreThanNByK([30, 10, 20, 20, 10, 20, 30, 30], 4).join(" "));
console.log(moreThanNByK([2, 2, 1, 2, 3, 2], 2).join(" "));

Output

20 30
2

Time O(n) · Space O(n)

Space-efficient method — O(nk) time, O(k) space. At most k − 1 values can appear more than n / k times (if k of them did, they would add up to more than n elements). So it is enough to track k − 1 candidates, in the style of the Boyer–Moore majority vote:

Candidate seen again
If arr[i] is already a candidate, increment its count.
Room for a new candidate
If fewer than k − 1 candidates are stored, add arr[i] with count 1.
Table full
Otherwise decrement every candidate's count and drop the ones that reach 0. This “cancels” k distinct values at once — the k − 1 candidates and arr[i].
Verify
A value with more than n / k occurrences cannot be cancelled away (each cancellation round consumes k distinct elements, so there are fewer than n / k rounds), but a survivor is not guaranteed to be frequent. Recount the real occurrences of each survivor in a second pass and keep those above n / k.

Python

def more_than_n_by_k(arr, k):
    n = len(arr)
    cand = {}                                  # at most k-1 candidates
    for x in arr:
        if x in cand:
            cand[x] += 1
        elif len(cand) < k - 1:
            cand[x] = 1
        else:                                  # table full: cancel k distinct values
            for key in list(cand):
                cand[key] -= 1
                if cand[key] == 0:
                    del cand[key]
    for key in cand:                           # second pass: real counts of the survivors
        cand[key] = 0
    for x in arr:
        if x in cand:
            cand[x] += 1
    return sorted(x for x, c in cand.items() if c > n // k)

print(" ".join(map(str, more_than_n_by_k([30, 10, 20, 20, 10, 20, 30, 30], 4))))
print(" ".join(map(str, more_than_n_by_k([2, 2, 1, 2, 3, 2], 2))))

C++

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

vector<int> moreThanNByK(const vector<int>& arr, int k) {
    int n = arr.size();
    unordered_map<int, int> cand;                        // at most k-1 candidates
    for (int x : arr) {
        auto it = cand.find(x);
        if (it != cand.end()) it->second++;
        else if ((int)cand.size() < k - 1) cand[x] = 1;
        else {                                           // table full: cancel k distinct values
            for (auto c = cand.begin(); c != cand.end();) {
                if (--c->second == 0) c = cand.erase(c);
                else ++c;
            }
        }
    }
    for (auto& [key, c] : cand) c = 0;                   // second pass: real counts of the survivors
    for (int x : arr) {
        auto it = cand.find(x);
        if (it != cand.end()) it->second++;
    }
    vector<int> res;
    for (auto& [x, c] : cand) if (c > n / k) res.push_back(x);
    sort(res.begin(), res.end());
    return res;
}

void print(const vector<int>& v) {
    for (size_t i = 0; i < v.size(); i++) cout << (i ? " " : "") << v[i];
    cout << "\n";
}

int main() {
    print(moreThanNByK({30, 10, 20, 20, 10, 20, 30, 30}, 4));
    print(moreThanNByK({2, 2, 1, 2, 3, 2}, 2));
}

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class Main {
    static List<Integer> moreThanNByK(int[] arr, int k) {
        int n = arr.length;
        Map<Integer, Integer> cand = new HashMap<>();            // at most k-1 candidates
        for (int x : arr) {
            if (cand.containsKey(x)) cand.merge(x, 1, Integer::sum);
            else if (cand.size() < k - 1) cand.put(x, 1);
            else {                                               // table full: cancel k distinct values
                Iterator<Map.Entry<Integer, Integer>> it = cand.entrySet().iterator();
                while (it.hasNext()) {
                    Map.Entry<Integer, Integer> e = it.next();
                    if (e.getValue() == 1) it.remove();
                    else e.setValue(e.getValue() - 1);
                }
            }
        }
        for (Map.Entry<Integer, Integer> e : cand.entrySet()) e.setValue(0);   // second pass
        for (int x : arr) if (cand.containsKey(x)) cand.merge(x, 1, Integer::sum);
        List<Integer> res = new ArrayList<>();
        for (Map.Entry<Integer, Integer> e : cand.entrySet())
            if (e.getValue() > n / k) res.add(e.getKey());
        Collections.sort(res);
        return res;
    }

    static void print(List<Integer> v) {
        StringBuilder sb = new StringBuilder();
        for (int x : v) sb.append(sb.length() == 0 ? "" : " ").append(x);
        System.out.println(sb);
    }

    public static void main(String[] args) {
        print(moreThanNByK(new int[]{30, 10, 20, 20, 10, 20, 30, 30}, 4));
        print(moreThanNByK(new int[]{2, 2, 1, 2, 3, 2}, 2));
    }
}

JavaScript

function moreThanNByK(arr, k) {
    const n = arr.length;
    const cand = new Map();                                // at most k-1 candidates
    for (const x of arr) {
        if (cand.has(x)) cand.set(x, cand.get(x) + 1);
        else if (cand.size < k - 1) cand.set(x, 1);
        else {                                             // table full: cancel k distinct values
            for (const [key, c] of [...cand]) {
                if (c === 1) cand.delete(key);
                else cand.set(key, c - 1);
            }
        }
    }
    for (const key of cand.keys()) cand.set(key, 0);       // second pass: real counts of the survivors
    for (const x of arr) if (cand.has(x)) cand.set(x, cand.get(x) + 1);
    const res = [];
    for (const [x, c] of cand) if (c > Math.floor(n / k)) res.push(x);
    return res.sort((a, b) => a - b);
}

console.log(moreThanNByK([30, 10, 20, 20, 10, 20, 30, 30], 4).join(" "));
console.log(moreThanNByK([2, 2, 1, 2, 3, 2], 2).join(" "));

Output

20 30
2

Time O(n · k) · Space O(k)

Interview Q&A

Why do the “longest subarray” problems store the first index of each prefix sum, while “subarray exists” only needs a set?

What is the worst-case time of these solutions, and does it matter?

When would you choose sorting over hashing for these problems?

The 0/1 subarray problem and the common-span problem look different from “subarray with sum 0” — how do you spot the reduction?

Explain why the n/k candidate method needs only k − 1 slots.