Loading…

easyArraysSometimes asked

Picking Numbers

Q: How do you solve Picking Numbers using the Brute Force — Try Every Element as the Group's Base approach?

When to use it: Good to state first: 'for each value present, count how many elements are within 1 of it.' Then note we can precompute those counts and skip the rescans. Start from the definition and don't be clever yet. A valid group has all elements within 1 of each other, so fix a base value `x` and ask: how many array elements are either `x` or `x+1`? Those are exactly the elements that could form a group whose minimum is `x`. **Why pick `x` and `x+1` rather than `x-1` and `x+1`.** If we counted `x-1`, `x`, and `x+1` together we'd allow a spread of 2 (an `x-1` and an `x+1` differ by 2), which violates the constraint. Anchoring `x` as the *minimum* of the group means the only other allowed value is `x+1`. Sweeping `x` over every element guarantees we also consider the group whose minimum is that smaller value, so nothing is missed. **The mechanics.** For each index `i`, set `x = a[i]`, then loop over all `j` and count how many `a[j]` equal `x` or `x+1`. Keep the running maximum of those counts. **Why we don't ship this.** With `n` up to a few hundred the `O(n²)` rescans are tolerable, but they repeat identical work: counting how many elements equal a given value over and over. Each distinct value's frequency is computed many times. Precomputing every value's frequency *once* removes the inner loop, which is the optimal solution below. Time complexity: O(n²). Space complexity: O(1).

Q: How do you solve Picking Numbers using the Frequency Array — Max Adjacent Bucket Sum (Optimal) approach?

When to use it: The answer they want. Phrase it as 'count every value once, then take the best count[v] + count[v+1]' — emphasize the two-adjacent-values insight. Tally how often each value appears in a fixed-size `count` array, then scan adjacent buckets and return the largest `count[v] + count[v+1]`. **The insight that makes it linear.** A group whose elements differ pairwise by at most 1 can contain at most *two distinct values*, and those two must be adjacent (`v` and `v+1`) — because any two values that are 2 or more apart violate the constraint. So we never need to consider arbitrary subsets; we only need to know, for each adjacent pair of values, how many elements they hold together. That's a frequency count plus a sliding sum of width 2 over the value axis. **Why a frequency array, not a hash map.** The values live in a small fixed range (0–99). A 101-entry `int[]` gives `O(1)` indexing with no hashing, no boxing, and perfect cache behavior. A hash map would also be `O(n)` but with constant-factor overhead that's pointless when the universe is this small. (If values could reach `10⁹`, you'd flip to a hash map of counts — call that out as the trade.) **Why we sum adjacent buckets instead of taking a single max.** Taking `max(count[v])` would answer 'most copies of one value', which is a valid group (spread 0) but often not the *largest*. Pairing each bucket with its right neighbor captures the better groups that mix `v` and `v+1`. The single-value case is still covered, because when `count[v+1]` is `0` the adjacent sum reduces to `count[v]` alone. **Why loop `v` only to the second-to-last bucket.** We read `count[v+1]`, so `v` must stop at `98` (or `len-2`) to keep `v+1` in bounds. Every group of the form `{v, v+1}` is still considered, including the group anchored at the top value, because that group's lower anchor is `v = top-1`. Time complexity: O(n). Space complexity: O(1).

Two Pointers · 24 of 30 · 7 min

Given an array of integers, find the longest subarray where the absolute difference between any two elements is less than or equal to 1.

Note: subsequences (any order, not necessarily contiguous) are allowed — you are choosing the largest group of elements, not a contiguous run. Return the size of that group.

In plain English

You are choosing the largest possible multiset of elements such that the max minus the min of the chosen elements is at most 1. Because the spread is capped at 1, every valid choice uses only some value v and possibly v+1. So the problem reduces to: which adjacent pair of values has the most elements combined?

Examples

Example 1

Input: a = [4, 6, 5, 3, 3, 1]
Output: 3
Note: Counts: 1→1, 3→2, 4→1, 5→1, 6→1. Best adjacent pair is 3 and 4 → 2 + 1 = 3 (the group {3, 3, 4}).

Example 2

Input: a = [1, 2, 2, 3, 1, 2]
Output: 5
Note: Counts: 1→2, 2→3, 3→1. Best adjacent pair is 1 and 2 → 2 + 3 = 5 (the group {1,1,2,2,2}).

Example 3

Input: a = [4, 97, 5, 97, 97, 4, 97, 4, 97, 97, 97]
Output: 7
Note: Counts: 4→3, 5→1, 97→7. Best is value 97 alone → 7 (its neighbor 96 has 0). Single-bucket answers happen when the neighbor is empty.

Constraints

2 ≤ n ≤ 100
0 ≤ a[i] < 100
The result is at least 1 (any single element trivially satisfies the condition)

Clarifying questions4First question: Does 'subarray' mean contiguous, or can I reorder / pick non-adjacent elements?Explore questions

Q1.Does 'subarray' mean contiguous, or can I reorder / pick non-adjacent elements?
Despite the word 'subarray', order does not matter and elements need not be contiguous — it's effectively the largest subset. That's why a frequency count works instead of a positional window.
Q2.Is the allowed difference strictly 1, or could it be a parameter k?
Here it's fixed at ≤ 1. That fixed, tiny bound is exactly what lets us say 'at most two adjacent values'.
Q3.What's the value range?
Small and bounded (0 to 99). That makes a fixed-size frequency array the natural data structure — O(1) indexing, no hashing overhead.
Q4.Can the array contain duplicates?
Yes, and duplicates are the point — count[v] tallies them so count[4]=3 means three 4's all pairwise-differ by 0.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

You want the longest subarray (any order allowed, so really the largest subset) where every pair differs by at most 1. Since values can differ by at most 1, the chosen elements use at most two distinct values v and v+1. Count the frequency of every value, then the answer is the maximum of count[v] + count[v+1] over all v. O(n) time using a fixed-size frequency array (values are bounded by 100).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realize that a maximum pairwise difference of 1 forces the chosen set to contain at most two distinct (adjacent) values — collapsing a search over subsets into a scan over value buckets.

Where candidates slip

Treating 'subarray' literally and writing a contiguous sliding window, or returning max single-value frequency and forgetting to add the adjacent bucket count[v]+count[v+1].

How to stand out

Say the key sentence: 'difference ≤ 1 means at most two adjacent values, so the answer is the best adjacent-bucket pair.' Then note the bounded value range justifies a frequency array over a hash map.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Try Every Element as the Group's Base	`O(n²)`	`O(1)`	Good to state first: 'for each value present, count how many elements are within 1 of it.' Then note we can precompute those counts and skip the rescans.	Read
2	Frequency Array — Max Adjacent Bucket Sum (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'count every value once, then take the best count[v] + count[v+1]' — emphasize the two-adjacent-values insight.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewLongest group with max pairwise diff ≤ 1How many distinct values can fit?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Try Every Element as the Group's Base

TimeO(n²)SpaceO(1)

Good to state first: 'for each value present, count how many elements are within 1 of it.' Then note we can precompute those counts and skip the rescans.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget the clever trick first. If you fixed one element x as the smallest in your group, which other elements could join it?

2Hint 2Explore hint

Any element equal to x or x+1 can join (difference ≤ 1). For each x in the array, scan the whole array and count elements in {x, x+1}.

3Hint 3Explore hint

Track the maximum such count over all choices of x. Two nested loops over n elements → O(n²).

A · Core idea

Start from the definition and don't be clever yet. A valid group has all elements within 1 of each other, so fix a base value x and ask: how many array elements are either x or x+1? Those are exactly the elements that could form a group whose minimum is x.

Why pick `x` and `x+1` rather than `x-1` and `x+1`. If we counted x-1, x, and x+1 together we'd allow a spread of 2 (an x-1 and an x+1 differ by 2), which violates the constraint. Anchoring x as the minimum of the group means the only other allowed value is x+1. Sweeping x over every element guarantees we also consider the group whose minimum is that smaller value, so nothing is missed.

The mechanics. For each index i, set x = a[i], then loop over all j and count how many a[j] equal x or x+1. Keep the running maximum of those counts.

Why we don't ship this. With n up to a few hundred the O(n²) rescans are tolerable, but they repeat identical work: counting how many elements equal a given value over and over. Each distinct value's frequency is computed many times. Precomputing every value's frequency once removes the inner loop, which is the optimal solution below.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [4, 6, 5, 3, 3, 1]

Array state

x = 3

highlight elements equal to 3 or 4

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

Reference implementation previewpublic int pickingNumbers(List<Integer> a) { int best = 0; for (int i = 0; i < a.size(); i++) { int x = a.get(i); int count = 0;Explore the full code

solution.javaJava

Brute Force — Try Every Element as the Group's Base — reference

3 teaching notes

1
public int pickingNumbers(List<Integer> a) {
2
    int best = 0;
3
    for (int i = 0; i < a.size(); i++) {
4
        // Treat x as the minimum of a candidate group — the only partner allowed is
5
        // x+1.
6
        int x = a.get(i);
7
        int count = 0;
8
        for (int j = 0; j < a.size(); j++) {
9
            int y = a.get(j);
10
            // Count elements within 1 of x while keeping x as the floor, so the spread
11
            // never exceeds 1.
12
            if (y == x || y == x + 1) {
13
                count++;
14
            }
15
        }
16
        // Keep the largest group found across all base values.
17
        best = Math.max(best, count);
18
    }
19
    return best;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

Anchoring x as the group's minimum (so the only partner value is x+1) is the move that keeps the spread ≤ 1 without casework. Once you see you're recomputing the same per-value counts repeatedly, the jump to a frequency array is natural.

ComplexityO(n²) time, O(1) space — For each of the n elements we rescan all n elements to tally how many are within 1 of it (specifically equal to it or one greater). That's n × n = O(n²) comparisons, with only a couple of counters for space.

E · Edge cases and pitfalls3Counting x-1, x, and x+1 together — allows a spread of 2 and over-counts.Explore edge cases

Pitfalls

Counting x-1, x, and x+1 together — allows a spread of 2 and over-counts.
Recomputing each value's frequency inside the inner loop — the wasted work this approach exists to expose.
Returning the base value instead of the group size.

03.2

Approach 2 of 2 · Optimal

Frequency Array — Max Adjacent Bucket Sum (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'count every value once, then take the best count[v] + count[v+1]' — emphasize the two-adjacent-values insight.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The brute force kept recomputing how many elements equal a given value. What if you computed every value's frequency exactly once up front?

2Hint 2Explore hint

Build count[] where count[v] is how many times v appears. Values are bounded (0..99) so a fixed-size array works.

3Hint 3Explore hint

A valid group uses only v and v+1. So the answer is the maximum of count[v] + count[v+1] over all v. One pass to count, one pass over buckets.

A · Core idea

Tally how often each value appears in a fixed-size count array, then scan adjacent buckets and return the largest count[v] + count[v+1].

The insight that makes it linear. A group whose elements differ pairwise by at most 1 can contain at most two distinct values, and those two must be adjacent (v and v+1) — because any two values that are 2 or more apart violate the constraint. So we never need to consider arbitrary subsets; we only need to know, for each adjacent pair of values, how many elements they hold together. That's a frequency count plus a sliding sum of width 2 over the value axis.

Why a frequency array, not a hash map. The values live in a small fixed range (0–99). A 101-entry int[] gives O(1) indexing with no hashing, no boxing, and perfect cache behavior. A hash map would also be O(n) but with constant-factor overhead that's pointless when the universe is this small. (If values could reach 10⁹, you'd flip to a hash map of counts — call that out as the trade.)

Why we sum adjacent buckets instead of taking a single max. Taking max(count[v]) would answer 'most copies of one value', which is a valid group (spread 0) but often not the largest. Pairing each bucket with its right neighbor captures the better groups that mix v and v+1. The single-value case is still covered, because when count[v+1] is 0 the adjacent sum reduces to count[v] alone.

Why loop `v` only to the second-to-last bucket. We read count[v+1], so v must stop at 98 (or len-2) to keep v+1 in bounds. Every group of the form {v, v+1} is still considered, including the group anchored at the top value, because that group's lower anchor is v = top-1.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [4, 6, 5, 3, 3, 1]

Array state

frequencies

count[v] for v = 0..6

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Frequency Array — Max Adjacent Bucket Sum (Optimal) — optimal

4 teaching notes

1
public int pickingNumbers(List<Integer> a) {
2
    // Fixed-size frequency array — values are bounded 0..99, so 101 slots cover v and
3
    // v+1 safely.
4
    int[] count = new int[101];
5
    for (int x : a) {
6
        // One pass tallies every value's frequency — no rescanning like the brute
7
        // force.
8
        count[x]++;
9
    }
10
    int best = 0;
11
    // Stop at 99 so count[v+1] stays in bounds — the off-by-one guard.
12
    for (int v = 0; v < 100; v++) {
13
        // Sum each adjacent bucket pair; the best pair is the largest valid group.
14
        best = Math.max(best, count[v] + count[v + 1]);
15
    }
16
    return best;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Bounded values + a tiny allowed spread = think in buckets, not windows. Counting frequencies converts 'find the largest valid subset' into 'find the best adjacent pair of counts', which is a one-line max. The same compression — replace a search over elements with a scan over a small value universe — drives Sock Merchant, counting sort, and any 'within k of each other for tiny k' problem.

ComplexityO(n) time, O(1) space — One pass over n elements to fill the frequency array, then one pass over the fixed 100 buckets to take the max adjacent sum. n + 100 work → O(n) time. The frequency array is a constant 101 entries → O(1) space (the universe size is fixed, not input-dependent).

E · Edge cases and pitfalls6a = [1, 1, 1, 1] — count[1]=4, count[2]=0 → max adjacent sum is 4 + 0 = 4. Single-value group handled because the empty neighbor contributes 0.Explore edge cases

Edge cases handled

a = [1, 1, 1, 1]count[1]=4, count[2]=0 → max adjacent sum is 4 + 0 = 4. Single-value group handled because the empty neighbor contributes 0.
a = [10, 12, 14]All values 2+ apart, every count is 1, no adjacent pair both nonzero → answer 1 (any single element).
a = [98, 99, 99]Tests the top of the range: v=98 reads count[98]+count[99]=1+2=3 without going out of bounds, confirming the loop bound is correct.

Pitfalls

Returning max(count[v]) instead of max(count[v] + count[v+1]) — misses groups that mix two adjacent values.
Looping v up to 100 and indexing count[v+1] out of bounds — stop at 99 / len-2.
Reaching for a hash map when the value range is tiny — a frequency array is simpler and faster here.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int pickingNumbers(List<Integer> a) { int[] count = new int[101]; for (int x : a) { count[x]++; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting to add the adjacent bucket

The largest group often mixes v and v+1. Taking only the single-value max returns the wrong answer on inputs like [4,4,5,5] where the true answer is 4, not 2.

Explore the code comparison

Don't write this

for (int v = 0; v <= 100; v++) {
    best = Math.max(best, count[v]);   // single value only
}

Write this instead

for (int v = 0; v < 100; v++) {
    best = Math.max(best, count[v] + count[v + 1]);
}

Including v-1, v, and v+1 together

A v-1 and a v+1 differ by 2, breaking the constraint. Only one adjacent pair may be combined at a time.

Explore the code comparison

Don't write this

best = max(best, count[v - 1] + count[v] + count[v + 1])

Write this instead

best = max(best, count[v] + count[v + 1])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Frequency count → max of adjacent-bucket sums

Code pattern to memorize

count = [0]*101
for x in a: count[x] += 1
best = max(count[v] + count[v+1] for v in range(100))

Rules to remember

1Allowed difference is ≤ 1, so any valid group uses at most two adjacent values v and v+1 — that's the whole insight.
2The answer is max(count[v] + count[v+1]), not max(count[v]) alone — pairing two adjacent buckets is what wins ties like [4,4,5,5].
3'Subarray' here is misleading: order doesn't matter and you may pick non-contiguous elements, so it's effectively a subset count.
4Values are bounded (0 ≤ a[i] ≤ 99 in the original), so a fixed frequency array beats a hash map — O(1) indexing, no hashing.
5Loop v only to 99 so v+1 stays in range — the classic off-by-one guard.

Use this pattern when

Pick the largest group whose values lie within a small fixed window of each other
Values come from a small bounded universe (ages, scores, small ints) → frequency array
Difference/threshold constraints of the form 'any two elements differ by at most k' with tiny k
You need a count of elements, not their positions

Choose another pattern when

Allowed difference k is large or unbounded → frequency-array windowing degrades; sort + sliding window over values instead
Elements must be contiguous in the original order (a true subarray) → this counting trick is wrong; use a real sliding window
Values are huge or sparse (e.g. up to 10⁹) → use a hash map of counts, not a 10⁹-size array

Interview takeaway

When the allowed spread is tiny and values are bounded, stop thinking 'windows' and start thinking 'buckets'. Counting frequencies and summing adjacent buckets turns a vague 'longest group' prompt into a one-line max — the bounded-value counting pattern you'll reuse in Sock Merchant, age histograms, and bucket sort.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBounded-Value Frequency Counting. Recognise it when values come from a small fixed universe and you must group by closeness. The trick is to count once into a frequency array, then answer the question as a tiny scan over buckets. Same shape as Sock Merchant, counting sort, and age-histogram problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Picking Numbers with difference ≤ k
Coming soon
Generalize to a window of width k+1 over the value buckets — a prefix-sum or sliding window across counts.
Frequency of the Most Frequent Element
Coming soon
Largest group you can make equal within a budget — sort then sliding window over values.
Sock Merchant
Same bounded-value frequency count, but you sum count // 2 over all buckets instead of adjacent pairs.

Same pattern

←

Minimum Swaps 2

Continue · Next problem

Count Inversions in an Array

easyArraysSometimes asked

Picking Numbers

Two Pointers · 24 of 30 · 7 min

Given an array of integers, find the longest subarray where the absolute difference between any two elements is less than or equal to 1.

Note: subsequences (any order, not necessarily contiguous) are allowed — you are choosing the largest group of elements, not a contiguous run. Return the size of that group.

In plain English

Examples

Example 1

Input: a = [4, 6, 5, 3, 3, 1]
Output: 3
Note: Counts: 1→1, 3→2, 4→1, 5→1, 6→1. Best adjacent pair is 3 and 4 → 2 + 1 = 3 (the group {3, 3, 4}).

Example 2

Input: a = [1, 2, 2, 3, 1, 2]
Output: 5
Note: Counts: 1→2, 2→3, 3→1. Best adjacent pair is 1 and 2 → 2 + 3 = 5 (the group {1,1,2,2,2}).

Example 3

Input: a = [4, 97, 5, 97, 97, 4, 97, 4, 97, 97, 97]
Output: 7
Note: Counts: 4→3, 5→1, 97→7. Best is value 97 alone → 7 (its neighbor 96 has 0). Single-bucket answers happen when the neighbor is empty.

Constraints

2 ≤ n ≤ 100
0 ≤ a[i] < 100
The result is at least 1 (any single element trivially satisfies the condition)

Clarifying questions4First question: Does 'subarray' mean contiguous, or can I reorder / pick non-adjacent elements?Explore questions

Q1.Does 'subarray' mean contiguous, or can I reorder / pick non-adjacent elements?
Despite the word 'subarray', order does not matter and elements need not be contiguous — it's effectively the largest subset. That's why a frequency count works instead of a positional window.
Q2.Is the allowed difference strictly 1, or could it be a parameter k?
Here it's fixed at ≤ 1. That fixed, tiny bound is exactly what lets us say 'at most two adjacent values'.
Q3.What's the value range?
Small and bounded (0 to 99). That makes a fixed-size frequency array the natural data structure — O(1) indexing, no hashing overhead.
Q4.Can the array contain duplicates?
Yes, and duplicates are the point — count[v] tallies them so count[4]=3 means three 4's all pairwise-differ by 0.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Treating 'subarray' literally and writing a contiguous sliding window, or returning max single-value frequency and forgetting to add the adjacent bucket count[v]+count[v+1].

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Try Every Element as the Group's Base	`O(n²)`	`O(1)`	Good to state first: 'for each value present, count how many elements are within 1 of it.' Then note we can precompute those counts and skip the rescans.	Read
2	Frequency Array — Max Adjacent Bucket Sum (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'count every value once, then take the best count[v] + count[v+1]' — emphasize the two-adjacent-values insight.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Try Every Element as the Group's Base

TimeO(n²)SpaceO(1)

Good to state first: 'for each value present, count how many elements are within 1 of it.' Then note we can precompute those counts and skip the rescans.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget the clever trick first. If you fixed one element x as the smallest in your group, which other elements could join it?

2Hint 2Explore hint

Any element equal to x or x+1 can join (difference ≤ 1). For each x in the array, scan the whole array and count elements in {x, x+1}.

3Hint 3Explore hint

Track the maximum such count over all choices of x. Two nested loops over n elements → O(n²).

A · Core idea

The mechanics. For each index i, set x = a[i], then loop over all j and count how many a[j] equal x or x+1. Keep the running maximum of those counts.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [4, 6, 5, 3, 3, 1]

Array state

x = 3

highlight elements equal to 3 or 4

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

Reference implementation previewpublic int pickingNumbers(List<Integer> a) { int best = 0; for (int i = 0; i < a.size(); i++) { int x = a.get(i); int count = 0;Explore the full code

solution.javaJava

Brute Force — Try Every Element as the Group's Base — reference

3 teaching notes

1
public int pickingNumbers(List<Integer> a) {
2
    int best = 0;
3
    for (int i = 0; i < a.size(); i++) {
4
        // Treat x as the minimum of a candidate group — the only partner allowed is
5
        // x+1.
6
        int x = a.get(i);
7
        int count = 0;
8
        for (int j = 0; j < a.size(); j++) {
9
            int y = a.get(j);
10
            // Count elements within 1 of x while keeping x as the floor, so the spread
11
            // never exceeds 1.
12
            if (y == x || y == x + 1) {
13
                count++;
14
            }
15
        }
16
        // Keep the largest group found across all base values.
17
        best = Math.max(best, count);
18
    }
19
    return best;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Counting x-1, x, and x+1 together — allows a spread of 2 and over-counts.Explore edge cases

Pitfalls

Counting x-1, x, and x+1 together — allows a spread of 2 and over-counts.
Recomputing each value's frequency inside the inner loop — the wasted work this approach exists to expose.
Returning the base value instead of the group size.

03.2

Approach 2 of 2 · Optimal

Frequency Array — Max Adjacent Bucket Sum (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'count every value once, then take the best count[v] + count[v+1]' — emphasize the two-adjacent-values insight.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The brute force kept recomputing how many elements equal a given value. What if you computed every value's frequency exactly once up front?

2Hint 2Explore hint

Build count[] where count[v] is how many times v appears. Values are bounded (0..99) so a fixed-size array works.

3Hint 3Explore hint

A valid group uses only v and v+1. So the answer is the maximum of count[v] + count[v+1] over all v. One pass to count, one pass over buckets.

A · Core idea

Tally how often each value appears in a fixed-size count array, then scan adjacent buckets and return the largest count[v] + count[v+1].

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [4, 6, 5, 3, 3, 1]

Array state

frequencies

count[v] for v = 0..6

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Frequency Array — Max Adjacent Bucket Sum (Optimal) — optimal

4 teaching notes

1
public int pickingNumbers(List<Integer> a) {
2
    // Fixed-size frequency array — values are bounded 0..99, so 101 slots cover v and
3
    // v+1 safely.
4
    int[] count = new int[101];
5
    for (int x : a) {
6
        // One pass tallies every value's frequency — no rescanning like the brute
7
        // force.
8
        count[x]++;
9
    }
10
    int best = 0;
11
    // Stop at 99 so count[v+1] stays in bounds — the off-by-one guard.
12
    for (int v = 0; v < 100; v++) {
13
        // Sum each adjacent bucket pair; the best pair is the largest valid group.
14
        best = Math.max(best, count[v] + count[v + 1]);
15
    }
16
    return best;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6a = [1, 1, 1, 1] — count[1]=4, count[2]=0 → max adjacent sum is 4 + 0 = 4. Single-value group handled because the empty neighbor contributes 0.Explore edge cases

Edge cases handled

a = [1, 1, 1, 1]count[1]=4, count[2]=0 → max adjacent sum is 4 + 0 = 4. Single-value group handled because the empty neighbor contributes 0.
a = [10, 12, 14]All values 2+ apart, every count is 1, no adjacent pair both nonzero → answer 1 (any single element).
a = [98, 99, 99]Tests the top of the range: v=98 reads count[98]+count[99]=1+2=3 without going out of bounds, confirming the loop bound is correct.

Pitfalls

Returning max(count[v]) instead of max(count[v] + count[v+1]) — misses groups that mix two adjacent values.
Looping v up to 100 and indexing count[v+1] out of bounds — stop at 99 / len-2.
Reaching for a hash map when the value range is tiny — a frequency array is simpler and faster here.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int pickingNumbers(List<Integer> a) { int[] count = new int[101]; for (int x : a) { count[x]++; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting to add the adjacent bucket

The largest group often mixes v and v+1. Taking only the single-value max returns the wrong answer on inputs like [4,4,5,5] where the true answer is 4, not 2.

Explore the code comparison

Don't write this

for (int v = 0; v <= 100; v++) {
    best = Math.max(best, count[v]);   // single value only
}

Write this instead

for (int v = 0; v < 100; v++) {
    best = Math.max(best, count[v] + count[v + 1]);
}

Including v-1, v, and v+1 together

A v-1 and a v+1 differ by 2, breaking the constraint. Only one adjacent pair may be combined at a time.

Explore the code comparison

Don't write this

best = max(best, count[v - 1] + count[v] + count[v + 1])

Write this instead

best = max(best, count[v] + count[v + 1])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Frequency count → max of adjacent-bucket sums

Code pattern to memorize

count = [0]*101
for x in a: count[x] += 1
best = max(count[v] + count[v+1] for v in range(100))

Rules to remember

1Allowed difference is ≤ 1, so any valid group uses at most two adjacent values v and v+1 — that's the whole insight.
2The answer is max(count[v] + count[v+1]), not max(count[v]) alone — pairing two adjacent buckets is what wins ties like [4,4,5,5].
3'Subarray' here is misleading: order doesn't matter and you may pick non-contiguous elements, so it's effectively a subset count.
4Values are bounded (0 ≤ a[i] ≤ 99 in the original), so a fixed frequency array beats a hash map — O(1) indexing, no hashing.
5Loop v only to 99 so v+1 stays in range — the classic off-by-one guard.

Use this pattern when

Pick the largest group whose values lie within a small fixed window of each other
Values come from a small bounded universe (ages, scores, small ints) → frequency array
Difference/threshold constraints of the form 'any two elements differ by at most k' with tiny k
You need a count of elements, not their positions

Choose another pattern when

Allowed difference k is large or unbounded → frequency-array windowing degrades; sort + sliding window over values instead
Elements must be contiguous in the original order (a true subarray) → this counting trick is wrong; use a real sliding window
Values are huge or sparse (e.g. up to 10⁹) → use a hash map of counts, not a 10⁹-size array

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Picking Numbers with difference ≤ k
Coming soon
Generalize to a window of width k+1 over the value buckets — a prefix-sum or sliding window across counts.
Frequency of the Most Frequent Element
Coming soon
Largest group you can make equal within a budget — sort then sliding window over values.
Sock Merchant
Same bounded-value frequency count, but you sum count // 2 over all buckets instead of adjacent pairs.

Same pattern

←

Minimum Swaps 2

Continue · Next problem

Count Inversions in an Array