Bulls and Cows: Hash Map Counting Explained

LeetCode 299, Bulls and Cows, is a medium-difficulty problem that asks you to compare two strings of digits and report how many are exact matches and how many are the right digit in the wrong position. If you have worked through frequency counting problems like Valid Anagram or Group Anagrams, the core technique here will feel familiar. The twist is that you need to track two separate categories of matches at the same time, and you need to be careful not to double-count digits that are already bulls.

The problem

You are playing a number guessing game. Your opponent picks a secret number, and you make a guess. Both are strings of digits with the same length. You need to return a hint in the format "xAyB", where:

• x is the number of bulls: digits in your guess that are the correct digit in the correct position.
• y is the number of cows: digits in your guess that are the correct digit but in the wrong position.

A digit can only be counted once. If it is already a bull, it cannot also be a cow.

Input:  secret = "1807", guess = "7810"
Output: "1A3B"  # 1 bull (8 matches), 3 cows (0, 1, 7)

At index 1, both strings have '8', so that is one bull. The digits '7', '1', and '0' all appear in both strings but at different positions, giving three cows. The digit '8' is excluded from the cow count because it is already a bull.

The brute force

The most natural first approach uses two passes. In the first pass, scan both strings in parallel and count the bulls (positions where secret[i] == guess[i]). Mark those positions as "used" so you do not count them again. In the second pass, for each non-bull digit in the guess, search through the non-bull digits in the secret for a match. When you find one, increment the cow count and mark that secret digit as used so it is not matched again.

This works correctly but has O(n^2) worst-case time because the inner search for each cow digit scans linearly through the remaining secret digits.

The key insight: single-pass counting

You can reduce this to a single pass with a frequency array of size 10 (one slot per digit 0 through 9). The idea is to track the "balance" between secret digits and guess digits that have not been matched as bulls. When secret[i] != guess[i], you increment the count for secret[i] and decrement the count for guess[i]. If the count for guess[i] was already positive before you decrement, that means the secret had an unmatched occurrence of that digit, so you have found a cow. Similarly, if the count for secret[i] was already negative before you increment, the guess had an unmatched occurrence, and that is also a cow.

This elegant trick lets you count both bulls and cows in a single loop with O(1) extra space (the fixed-size array).

Step-by-step walkthrough

Let's trace through the example with secret = "1807" and guess = "7810" using the two-pass approach, which is easier to follow visually.

The single-pass version produces the same result but combines both passes into one loop. Each time secret[i] != guess[i], it updates the frequency array and checks whether the new digits cancel existing surpluses.

The code

def getHint(secret: str, guess: str) -> str:
    bulls = 0
    cows = 0
    count = [0] * 10

    for s, g in zip(secret, guess):
        if s == g:
            bulls += 1
        else:
            if count[int(s)] < 0:
                cows += 1
            if count[int(g)] > 0:
                cows += 1
            count[int(s)] += 1
            count[int(g)] -= 1

    return f"{bulls}A{cows}B"

1. Initialize counters. bulls and cows start at 0. The count array has 10 slots (digits 0 through 9), all initialized to zero.
2. Iterate in parallel. For each position, compare s (secret digit) and g (guess digit).
3. Bull check. If they are equal, increment bulls and move on. No frequency update needed.
4. Cow detection for secret digit. If count[int(s)] is negative, the guess previously had an unmatched copy of this digit. That copy just found its match, so increment cows.
5. Cow detection for guess digit. If count[int(g)] is positive, the secret previously had an unmatched copy of this digit. That copy just found its match, so increment cows.
6. Update counts. Increment count[int(s)] (secret contributed a digit) and decrement count[int(g)] (guess consumed a digit).
7. Format result. Return the string in "xAyB" format.

Complexity analysis

Time: O(n), where n is the length of the strings. You iterate through both strings once, and each operation inside the loop is O(1).

Space: O(1). The count array has exactly 10 elements regardless of input size.

Common mistakes

1. Double-counting bulls as cows. If you count frequency for all digits first and then subtract bulls, you can get the cow count wrong. Always exclude bull positions from the cow counting logic entirely.

2. Forgetting that each digit can only match once. If the secret has one '1' and the guess has three '1's (none at the same position), only one is a cow. The frequency array naturally handles this, but a naive nested loop can overcount if you do not mark digits as used.

3. Checking cow conditions after updating counts instead of before. In the single-pass approach, the order matters. You must check whether count[int(s)] < 0 before incrementing, and whether count[int(g)] > 0 before decrementing. Reversing this order breaks the logic.

4. Using a dictionary instead of a fixed array. This is not wrong, but it adds unnecessary overhead. Since digits are always 0 through 9, a fixed-size list of 10 integers is cleaner and faster.

The building blocks

Frequency balance counting

count = [0] * k
for a, b in zip(seq1, seq2):
    if count[a] < 0:
        matches += 1
    if count[b] > 0:
        matches += 1
    count[a] += 1
    count[b] -= 1

This pattern tracks the net surplus between two sequences in a single pass. Positive values mean seq1 has unmatched elements; negative values mean seq2 has unmatched elements. When a new element from one sequence cancels an existing surplus from the other, you have found a cross-match.

You will see this technique in problems that ask you to compare two sequences and count shared elements without regard to position. It also appears in variations of anagram detection within sliding windows, where you track the balance of characters as the window shifts.

Edge cases

• All bulls. If secret and guess are identical, every digit is a bull and the cow count is 0. The count array stays all zeros.
• No bulls, all cows. If every digit appears in both strings but none are at the same index, cows equals the total number of matchable digits. The frequency array handles the matching correctly.
• Repeated digits. Secret = "1122", guess = "2211". Bulls = 0, cows = 4. Each digit in the guess finds a counterpart in the secret at a different position.
• Partial repeats. Secret = "1122", guess = "1222". Bulls = 2 (indices 2 and 3). Cow = 1 (one of the two '2's in the guess matches the '1' ... wait, no. Carefully: index 0 has '1' vs '1', that is a bull. Index 1 has '1' vs '2', not a bull. Index 2 has '2' vs '2', bull. Index 3 has '2' vs '2', bull. So bulls = 3, cows = 0.
• No matches at all. Secret = "1234", guess = "5678". Bulls = 0, cows = 0.
• Single digit. Secret = "1", guess = "1" gives "1A0B". Secret = "1", guess = "2" gives "0A0B".

From understanding to recall

Bulls and Cows is a great problem for building intuition about frequency counting with a fixed-size array. The single-pass approach is clever, and it is the kind of trick that slips out of memory if you do not revisit it. The next time you see a problem that compares two sequences element by element, you want the frequency balance pattern to surface automatically.

Spaced repetition locks in both the algorithm and the implementation details. Practicing the single-pass version from scratch at increasing intervals ensures that the check-before-update order and the sign conventions become second nature. When you encounter a similar matching problem in an interview, you will reach for the right tool without hesitation.

Related posts

• Group Anagrams - Another hash map counting problem with character frequencies
• Valid Anagram - The simpler version of frequency counting
• Contains Duplicate - Basic hash set/map usage for detecting matches

Mastering frequency-based matching is one of the most transferable skills in coding interviews. If you want to drill this pattern and related hash map techniques until they are automatic, CodeBricks uses spaced repetition to schedule reviews right when you are about to forget.