Loading…

easyArraysSometimes asked

Migratory Birds

Q: How do you solve Migratory Birds using the Brute Force — Recount Each Candidate Id approach?

When to use it: Worth a sentence to show the naive shape, then collapse it: 'but I can count all ids in a single pass instead of one scan per id.' The most literal approach: there are only five possible answers, so for each id `t` in `1..5`, scan the whole array and count how many elements equal `t`. Keep the id with the largest count. **Handling the tiebreak naturally.** Iterate candidate ids from `1` up to `5`, and only replace the current best when you find a *strictly* larger count. Because you start from the smallest id and never overwrite on equality, a tie automatically resolves to the smaller id. **Why it works but isn't ideal.** Each candidate triggers a full pass, so the array is traversed five times. The counts you need are all derivable in a single pass — recounting per id is redundant. With ids bounded to five it's only a constant factor, but the one-pass frequency array is cleaner and the habit matters when the universe is large. Time complexity: O(5n) = O(n). Space complexity: O(1).

Q: How do you solve Migratory Birds using the Frequency Array — One-Pass Count + Argmax (Optimal) approach?

When to use it: The answer they want. Phrase it as 'tally all ids in one pass, then take the argmax over the five buckets, smallest id on ties.' Tally every id in one pass into a fixed-size `count` array, then scan the five id slots and return the id with the largest count, resolving ties to the smaller id. **Why a size-6 array.** Ids run `1..5`, so a 6-slot array (leaving index 0 unused) lets us write `count[id]++` with `id` as a direct index — no hashing, no bounds gymnastics. The universe is fixed and tiny, so this is `O(1)` space, not `O(n)`. **The tiebreak, made airtight.** After counting, we want the id with the maximum count, smallest id on ties. Two design choices guarantee that with zero special-casing: (1) scan ids in *increasing* order `1 → 5`, and (2) update the best only on a *strict* `count[id] > best`. When two ids tie, the smaller one is visited first and stored; the later equal id fails the strict `>` test and is rejected. Flip to `>=` and the *last* (largest) tied id wins instead — the single most common bug in this problem. **Why initialize best to id 1.** We seed `bestId = 1` and compare from id `2` upward (or seed with a count of `-1` and start at id `1`). Either way the loop is well-defined and the smallest valid id is the default winner if everything ties. Initializing `bestId` to `0` would be wrong because `0` is not a real bird id. **Why this beats the brute force.** Same asymptotic class, but a single array traversal instead of five, and the counting and tiebreak concerns are cleanly separated. It also generalizes: if ids became unbounded you'd swap the array for a hash map and keep the identical strict-`>` argmax. Time complexity: O(n). Space complexity: O(1).

Two Pointers · 21 of 30 · 6 min

There are five types of migratory birds, identified by ids 1 through 5. Given an array arr where each element is the type id of a bird sighted, return the id of the bird type that was sighted the most. If more than one type shares the maximum count, return the smallest such id.

In plain English

You are computing the mode of a list of ids drawn from the fixed set {1,2,3,4,5}, with ties resolved toward the smaller id. The bounded id range is the key structural fact: counting is a fixed-size array, and the argmax is a five-way comparison.

Examples

Example 1

Input: arr = [1, 4, 4, 4, 5, 3]
Output: 4
Note: Counts: 1→1, 3→1, 4→3, 5→1. Type 4 has the most sightings (3).

Example 2

Input: arr = [1, 2, 3, 4, 5, 4, 3, 2, 1, 3, 4]
Output: 3
Note: Counts: 1→2, 2→2, 3→3, 4→3, 5→1. Types 3 and 4 tie at 3 → return the smaller id, 3.

Example 3

Input: arr = [2, 2, 1, 1]
Output: 1
Note: Types 1 and 2 both appear twice → tie resolved to the smaller id, 1.

Constraints

5 ≤ n ≤ 2 × 10⁵
1 ≤ arr[i] ≤ 5
It is guaranteed at least one bird of some type is sighted

Clarifying questions4First question: How are ties resolved?Explore questions

Q1.How are ties resolved?
Return the smallest id among those tied for the maximum count. This is the detail that determines whether you use < / > / >= in the argmax.
Q2.Are ids always within 1..5?
Yes in this problem. That bounded range lets a size-6 array (index 0 unused) act as the counter with O(1) indexing.
Q3.Can a type have zero sightings?
Yes — some of the five ids may never appear. Their counts stay 0 and they simply lose the argmax.
Q4.What if all five appear equally often?
Then they're all tied and we return id 1, the smallest. The ascending scan with strict > guarantees that.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Count how often each bird type id appears, then return the id with the highest count — breaking ties toward the smallest id. With only 5 types you can use a fixed 6-slot frequency array (ids 1..5). One pass to count, one pass over the small id range to take the argmax, scanning ids in increasing order so the first maximum found is automatically the smallest. O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you count with the right data structure for a tiny bounded id space and, more importantly, whether you implement the smallest-id tiebreak correctly with a strict comparison and increasing scan order.

Where candidates slip

Using >= when comparing counts (returns the largest id on ties, not the smallest), or scanning ids in arbitrary/decreasing order so the tiebreak is wrong.

How to stand out

State the tiebreak invariant explicitly: 'I scan ids ascending and only replace on a strict greater-than, so ties resolve to the smallest id for free.' Note the bounded id range justifies an array over a 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 — Recount Each Candidate Id	`O(5n) = O(n)`	`O(1)`	Worth a sentence to show the naive shape, then collapse it: 'but I can count all ids in a single pass instead of one scan per id.'	Read
2	Frequency Array — One-Pass Count + Argmax (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'tally all ids in one pass, then take the argmax over the five buckets, smallest id on ties.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewBird sightings arraycount[id] strictly > best so far?YesNo (incl. equal)Explore 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 — Recount Each Candidate Id

TimeO(5n) = O(n)SpaceO(1)

Worth a sentence to show the naive shape, then collapse it: 'but I can count all ids in a single pass instead of one scan per id.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget cleverness: for each possible id 1..5, how many times does it appear?

2Hint 2Explore hint

For each candidate id, scan the whole array and count occurrences of that id.

3Hint 3Explore hint

Track the id with the largest count, scanning candidates in increasing order so ties keep the smaller id.

A · Core idea

The most literal approach: there are only five possible answers, so for each id t in 1..5, scan the whole array and count how many elements equal t. Keep the id with the largest count.

Handling the tiebreak naturally. Iterate candidate ids from 1 up to 5, and only replace the current best when you find a strictly larger count. Because you start from the smallest id and never overwrite on equality, a tie automatically resolves to the smaller id.

Why it works but isn't ideal. Each candidate triggers a full pass, so the array is traversed five times. The counts you need are all derivable in a single pass — recounting per id is redundant. With ids bounded to five it's only a constant factor, but the one-pass frequency array is cleaner and the habit matters when the universe is large.

B · Visual dry run

Interactive dry run

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

arr = [1, 4, 4, 4, 5, 3]

Array state

id = 4

highlight every element equal to 4

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

Reference implementation previewpublic int migratoryBirds(List<Integer> arr) { int bestId = 1; int bestCount = -1; for (int id = 1; id <= 5; id++) { int c = 0;Explore the full code

solution.javaJava

Brute Force — Recount Each Candidate Id — reference

2 teaching notes

1
public int migratoryBirds(List<Integer> arr) {
2
    int bestId = 1;
3
    int bestCount = -1;
4
    // Candidate ids in increasing order — foundation of the smallest-id tiebreak.
5
    for (int id = 1; id <= 5; id++) {
6
        int c = 0;
7
        for (int t : arr) {
8
            if (t == id) {
9
                c++;
10
            }
11
        }
12
        // Strict > means an equal count never overwrites the already-found smaller id.
13
        if (c > bestCount) {
14
            bestCount = c;
15
            bestId = id;
16
        }
17
    }
18
    return bestId;
19
}

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

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

Even the naive version teaches the tiebreak discipline: ascending candidate order + strict-greater update = smallest-id-wins. That rule carries over unchanged to the optimal solution.

ComplexityO(5n) = O(n) time, O(1) space — Five candidate ids, each requiring a full O(n) scan of the array → 5n operations. Since 5 is a constant this is technically O(n), but it reads the array five times instead of once.

E · Edge cases and pitfalls3Using >= and accidentally returning the largest id on ties.Explore edge cases

Pitfalls

Using >= and accidentally returning the largest id on ties.
Scanning candidate ids in decreasing order, which also breaks the tiebreak.
Re-reading the array five times when one pass suffices.

03.2

Approach 2 of 2 · Optimal

Frequency Array — One-Pass Count + Argmax (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'tally all ids in one pass, then take the argmax over the five buckets, smallest id on ties.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of one pass per id, can you tally all five ids in a single pass?

2Hint 2Explore hint

Use count[] of size 6 (indices 1..5). One loop increments count[arr[i]].

3Hint 3Explore hint

Then sweep ids 1..5 in order, keeping the id whose count is strictly greatest — ascending order plus strict > gives the smallest-id tiebreak.

A · Core idea

Tally every id in one pass into a fixed-size count array, then scan the five id slots and return the id with the largest count, resolving ties to the smaller id.

Why a size-6 array. Ids run 1..5, so a 6-slot array (leaving index 0 unused) lets us write count[id]++ with id as a direct index — no hashing, no bounds gymnastics. The universe is fixed and tiny, so this is O(1) space, not O(n).

The tiebreak, made airtight. After counting, we want the id with the maximum count, smallest id on ties. Two design choices guarantee that with zero special-casing: (1) scan ids in increasing order 1 → 5, and (2) update the best only on a strict count[id] > best. When two ids tie, the smaller one is visited first and stored; the later equal id fails the strict > test and is rejected. Flip to >= and the last (largest) tied id wins instead — the single most common bug in this problem.

Why initialize best to id 1. We seed bestId = 1 and compare from id 2 upward (or seed with a count of -1 and start at id 1). Either way the loop is well-defined and the smallest valid id is the default winner if everything ties. Initializing bestId to 0 would be wrong because 0 is not a real bird id.

Why this beats the brute force. Same asymptotic class, but a single array traversal instead of five, and the counting and tiebreak concerns are cleanly separated. It also generalizes: if ids became unbounded you'd swap the array for a hash map and keep the identical strict-> argmax.

B · Visual dry run

Interactive dry run

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

arr = [1, 2, 3, 4, 5, 4, 3, 2, 1, 3, 4]

Array state

counts

count[id] for id = 0..5 (0 unused)

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Frequency Array — One-Pass Count + Argmax (Optimal) — optimal

5 teaching notes

1
public int migratoryBirds(List<Integer> arr) {
2
    // Slots 1..5 hold each type's tally; index 0 is unused. Fixed size → O(1) space.
3
    int[] count = new int[6];
4
    for (int t : arr) {
5
        // Single pass tallies all five ids — no per-id rescans.
6
        count[t]++;
7
    }
8
    // Seed with the smallest id so it wins by default if every count ties.
9
    int bestId = 1;
10
    // Sweep remaining ids in increasing order — the basis of the tiebreak.
11
    for (int id = 2; id <= 5; id++) {
12
        // Strict > only replaces on a true majority; equal counts keep the smaller
13
        // bestId.
14
        if (count[id] > count[bestId]) {
15
            bestId = id;
16
        }
17
    }
18
    return bestId;
19
}

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

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

The whole problem is 'mode with a tiebreak', and the tiebreak is not extra code — it falls out of scan order and comparison strictness. Internalize that 'ascending scan + strict greater-than ⇒ smallest key wins ties' and you can resolve any deterministic tiebreak by choosing the scan direction and comparator to match. The same argmax discipline appears in voting/mode problems and in Dijkstra-style 'smallest-id-first' selection.

ComplexityO(n) time, O(1) space — One pass over n elements to fill the count array, then a constant 5-element sweep for the argmax → O(n) time. The count array is a fixed 6 entries regardless of n → O(1) space.

E · Edge cases and pitfalls6arr = [5, 5, 5, 5] — Only id 5 appears (count 4). All other counts 0; id 5 wins the argmax. Confirms unseen ids with count 0 are handled.Explore edge cases

Edge cases handled

arr = [5, 5, 5, 5]Only id 5 appears (count 4). All other counts 0; id 5 wins the argmax. Confirms unseen ids with count 0 are handled.
arr = [1, 2, 3, 4, 5]All five tie at 1 → ascending strict-> scan never replaces id 1 → returns 1, the smallest id.
arr = [3, 3, 2, 2]Ids 2 and 3 tie at 2 → returns 2. Demonstrates the tiebreak even when the smaller tied id appears later in the array.

Pitfalls

Using >= so the largest tied id wins instead of the smallest.
Initializing bestId to 0 (not a real id) or scanning ids in the wrong order.
Sizing the array to 5 and indexing count[5] out of bounds — you need size 6 for ids 1..5.

Practice

Try the solution yourself

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

Editable code previewpublic int migratoryBirds(List<Integer> arr) { int[] count = new int[6]; for (int t : arr) { count[t]++; }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.

The >= tiebreak flip

On a tie, >= overwrites the current best with the equal, larger id — returning the largest tied id instead of the required smallest.

Explore the code comparison

Don't write this

if (count[id] >= count[bestId]) {   // largest id wins ties
    bestId = id;
}

Write this instead

if (count[id] > count[bestId]) {    // smallest id wins ties
    bestId = id;
}

Array too small for the id range

Ids go up to 5, so count must have index 5. A size-5 array (indices 0..4) throws on count[5].

Explore the code comparison

Don't write this

count = [0] * 5   # indices 0..4, no slot for id 5
count[t] += 1

Write this instead

count = [0] * 6   # indices 0..5, id 5 fits
count[t] += 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Frequency count → argmax with smallest-id tiebreak

Code pattern to memorize

count = [0]*6          # ids 1..5
for t in birds: count[t] += 1
best_id, best_count = 1, count[1]
for t in range(2, 6):
    if count[t] > best_count:    # strict > keeps the smaller id on ties
        best_id, best_count = t, count[t]

Rules to remember

1Tie-break toward the smallest id: scan ids in increasing order and update only on a strict >, so an equal count never replaces an already-found smaller id.
2Ids are 1..5 (a fixed tiny universe) → a frequency array of size 6 beats a hash map; index 0 is unused.
3Initialize best_id to the smallest id (1), not 0 — id 0 doesn't exist and would never be returned correctly.
4Using >= instead of > silently flips the tiebreak to the largest id — the #1 trap here.
5If ids were unbounded you'd swap the array for a hash map but keep the exact same strict-> argmax.

Use this pattern when

Return the most frequent item, with a deterministic tiebreak rule
The item universe is small and bounded (categories, ratings 1..5, days of week)
Mode / argmax over counts
You need the key, not the count

Choose another pattern when

You need the top-K most frequent, not just the single mode → bucket sort or a heap
Ids are huge or sparse → hash map of counts instead of a fixed array
Tiebreak is by something other than id (e.g. earliest seen) → track that signal explicitly

Interview takeaway

Most-frequent-with-a-tiebreak is a frequency count plus a disciplined argmax. The entire correctness of the tiebreak lives in two choices: scan order and whether you compare with `>` or `>=`. Get those right and you've solved a whole family of mode problems.

Continue

Transfer the pattern to another problem

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

Transferable patternFrequency Count → Argmax with Tiebreak. Recognise it on any 'most frequent item, ties broken by rule X' prompt. Count into a bounded array (or hash map), then choose scan order and comparison strictness so the tiebreak falls out for free. Same shape as Majority Element and Top K Frequent.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Majority Element
Find the element appearing more than n/2 times — Boyer–Moore voting in O(1) space.
Top K Frequent Elements
Coming soon
Generalize the argmax to top-K with bucket sort or a heap over the counts.
Sock Merchant
Another bounded-value frequency count, summing count // 2 instead of taking an argmax.

Same pattern

←

Fraudulent Activity Notifications

Continue · Next problem

Minimum Absolute Difference in an Array

easyArraysSometimes asked

Migratory Birds

Two Pointers · 21 of 30 · 6 min

In plain English

Examples

Example 1

Input: arr = [1, 4, 4, 4, 5, 3]
Output: 4
Note: Counts: 1→1, 3→1, 4→3, 5→1. Type 4 has the most sightings (3).

Example 2

Input: arr = [1, 2, 3, 4, 5, 4, 3, 2, 1, 3, 4]
Output: 3
Note: Counts: 1→2, 2→2, 3→3, 4→3, 5→1. Types 3 and 4 tie at 3 → return the smaller id, 3.

Example 3

Input: arr = [2, 2, 1, 1]
Output: 1
Note: Types 1 and 2 both appear twice → tie resolved to the smaller id, 1.

Constraints

5 ≤ n ≤ 2 × 10⁵
1 ≤ arr[i] ≤ 5
It is guaranteed at least one bird of some type is sighted

Clarifying questions4First question: How are ties resolved?Explore questions

Q1.How are ties resolved?
Return the smallest id among those tied for the maximum count. This is the detail that determines whether you use < / > / >= in the argmax.
Q2.Are ids always within 1..5?
Yes in this problem. That bounded range lets a size-6 array (index 0 unused) act as the counter with O(1) indexing.
Q3.Can a type have zero sightings?
Yes — some of the five ids may never appear. Their counts stay 0 and they simply lose the argmax.
Q4.What if all five appear equally often?
Then they're all tied and we return id 1, the smallest. The ascending scan with strict > guarantees that.

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

Using >= when comparing counts (returns the largest id on ties, not the smallest), or scanning ids in arbitrary/decreasing order so the tiebreak is wrong.

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 — Recount Each Candidate Id	`O(5n) = O(n)`	`O(1)`	Worth a sentence to show the naive shape, then collapse it: 'but I can count all ids in a single pass instead of one scan per id.'	Read
2	Frequency Array — One-Pass Count + Argmax (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'tally all ids in one pass, then take the argmax over the five buckets, smallest id on ties.'	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 — Recount Each Candidate Id

TimeO(5n) = O(n)SpaceO(1)

Worth a sentence to show the naive shape, then collapse it: 'but I can count all ids in a single pass instead of one scan per id.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget cleverness: for each possible id 1..5, how many times does it appear?

2Hint 2Explore hint

For each candidate id, scan the whole array and count occurrences of that id.

3Hint 3Explore hint

Track the id with the largest count, scanning candidates in increasing order so ties keep the smaller id.

A · Core idea

The most literal approach: there are only five possible answers, so for each id t in 1..5, scan the whole array and count how many elements equal t. Keep the id with the largest count.

B · Visual dry run

Interactive dry run

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

arr = [1, 4, 4, 4, 5, 3]

Array state

id = 4

highlight every element equal to 4

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

Reference implementation previewpublic int migratoryBirds(List<Integer> arr) { int bestId = 1; int bestCount = -1; for (int id = 1; id <= 5; id++) { int c = 0;Explore the full code

solution.javaJava

Brute Force — Recount Each Candidate Id — reference

2 teaching notes

1
public int migratoryBirds(List<Integer> arr) {
2
    int bestId = 1;
3
    int bestCount = -1;
4
    // Candidate ids in increasing order — foundation of the smallest-id tiebreak.
5
    for (int id = 1; id <= 5; id++) {
6
        int c = 0;
7
        for (int t : arr) {
8
            if (t == id) {
9
                c++;
10
            }
11
        }
12
        // Strict > means an equal count never overwrites the already-found smaller id.
13
        if (c > bestCount) {
14
            bestCount = c;
15
            bestId = id;
16
        }
17
    }
18
    return bestId;
19
}

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

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

Even the naive version teaches the tiebreak discipline: ascending candidate order + strict-greater update = smallest-id-wins. That rule carries over unchanged to the optimal solution.

E · Edge cases and pitfalls3Using >= and accidentally returning the largest id on ties.Explore edge cases

Pitfalls

Using >= and accidentally returning the largest id on ties.
Scanning candidate ids in decreasing order, which also breaks the tiebreak.
Re-reading the array five times when one pass suffices.

03.2

Approach 2 of 2 · Optimal

Frequency Array — One-Pass Count + Argmax (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'tally all ids in one pass, then take the argmax over the five buckets, smallest id on ties.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of one pass per id, can you tally all five ids in a single pass?

2Hint 2Explore hint

Use count[] of size 6 (indices 1..5). One loop increments count[arr[i]].

3Hint 3Explore hint

Then sweep ids 1..5 in order, keeping the id whose count is strictly greatest — ascending order plus strict > gives the smallest-id tiebreak.

A · Core idea

Tally every id in one pass into a fixed-size count array, then scan the five id slots and return the id with the largest count, resolving ties to the smaller id.

B · Visual dry run

Interactive dry run

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

arr = [1, 2, 3, 4, 5, 4, 3, 2, 1, 3, 4]

Array state

counts

count[id] for id = 0..5 (0 unused)

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Frequency Array — One-Pass Count + Argmax (Optimal) — optimal

5 teaching notes

1
public int migratoryBirds(List<Integer> arr) {
2
    // Slots 1..5 hold each type's tally; index 0 is unused. Fixed size → O(1) space.
3
    int[] count = new int[6];
4
    for (int t : arr) {
5
        // Single pass tallies all five ids — no per-id rescans.
6
        count[t]++;
7
    }
8
    // Seed with the smallest id so it wins by default if every count ties.
9
    int bestId = 1;
10
    // Sweep remaining ids in increasing order — the basis of the tiebreak.
11
    for (int id = 2; id <= 5; id++) {
12
        // Strict > only replaces on a true majority; equal counts keep the smaller
13
        // bestId.
14
        if (count[id] > count[bestId]) {
15
            bestId = id;
16
        }
17
    }
18
    return bestId;
19
}

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

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

E · Edge cases and pitfalls6arr = [5, 5, 5, 5] — Only id 5 appears (count 4). All other counts 0; id 5 wins the argmax. Confirms unseen ids with count 0 are handled.Explore edge cases

Edge cases handled

arr = [5, 5, 5, 5]Only id 5 appears (count 4). All other counts 0; id 5 wins the argmax. Confirms unseen ids with count 0 are handled.
arr = [1, 2, 3, 4, 5]All five tie at 1 → ascending strict-> scan never replaces id 1 → returns 1, the smallest id.
arr = [3, 3, 2, 2]Ids 2 and 3 tie at 2 → returns 2. Demonstrates the tiebreak even when the smaller tied id appears later in the array.

Pitfalls

Using >= so the largest tied id wins instead of the smallest.
Initializing bestId to 0 (not a real id) or scanning ids in the wrong order.
Sizing the array to 5 and indexing count[5] out of bounds — you need size 6 for ids 1..5.

Practice

Try the solution yourself

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

Editable code previewpublic int migratoryBirds(List<Integer> arr) { int[] count = new int[6]; for (int t : arr) { count[t]++; }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.

The >= tiebreak flip

On a tie, >= overwrites the current best with the equal, larger id — returning the largest tied id instead of the required smallest.

Explore the code comparison

Don't write this

if (count[id] >= count[bestId]) {   // largest id wins ties
    bestId = id;
}

Write this instead

if (count[id] > count[bestId]) {    // smallest id wins ties
    bestId = id;
}

Array too small for the id range

Ids go up to 5, so count must have index 5. A size-5 array (indices 0..4) throws on count[5].

Explore the code comparison

Don't write this

count = [0] * 5   # indices 0..4, no slot for id 5
count[t] += 1

Write this instead

count = [0] * 6   # indices 0..5, id 5 fits
count[t] += 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Frequency count → argmax with smallest-id tiebreak

Code pattern to memorize

count = [0]*6          # ids 1..5
for t in birds: count[t] += 1
best_id, best_count = 1, count[1]
for t in range(2, 6):
    if count[t] > best_count:    # strict > keeps the smaller id on ties
        best_id, best_count = t, count[t]

Rules to remember

1Tie-break toward the smallest id: scan ids in increasing order and update only on a strict >, so an equal count never replaces an already-found smaller id.
2Ids are 1..5 (a fixed tiny universe) → a frequency array of size 6 beats a hash map; index 0 is unused.
3Initialize best_id to the smallest id (1), not 0 — id 0 doesn't exist and would never be returned correctly.
4Using >= instead of > silently flips the tiebreak to the largest id — the #1 trap here.
5If ids were unbounded you'd swap the array for a hash map but keep the exact same strict-> argmax.

Use this pattern when

Return the most frequent item, with a deterministic tiebreak rule
The item universe is small and bounded (categories, ratings 1..5, days of week)
Mode / argmax over counts
You need the key, not the count

Choose another pattern when

You need the top-K most frequent, not just the single mode → bucket sort or a heap
Ids are huge or sparse → hash map of counts instead of a fixed array
Tiebreak is by something other than id (e.g. earliest seen) → track that signal explicitly

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

Majority Element
Find the element appearing more than n/2 times — Boyer–Moore voting in O(1) space.
Top K Frequent Elements
Coming soon
Generalize the argmax to top-K with bucket sort or a heap over the counts.
Sock Merchant
Another bounded-value frequency count, summing count // 2 instead of taking an argmax.

Same pattern

←

Fraudulent Activity Notifications

Continue · Next problem

Minimum Absolute Difference in an Array