How do you solve Bulls and Cows on LeetCode?

Bulls and Cows (LeetCode #299) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Bulls are counted directly by comparing positions.

What is the brute force solution for Bulls and Cows?

The brute force approach for Bulls and Cows is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each digit in the guess against the secret. For each digit, we count bulls and cows by comparing positions and counting occurrences of unmatched digits. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Bulls and Cows?

Bulls and Cows uses the following concepts: Hash Table, String, Counting. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Bulls and Cows?

Clarify how to handle duplicates in the guess and secret. Discuss edge cases, such as all digits being bulls or cows. Practice explaining your thought process while coding.

What are common mistakes when solving Bulls and Cows?

Counting cows incorrectly by not considering the frequency of unmatched digits. Not resetting counts for each new guess.

#299

Bulls and Cows

Medium

Hash TableStringCountingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a single pass to count bulls and then uses arrays to track unmatched digits, allowing us to calculate cows efficiently without nested loops.

⚙️

Algorithm

3 steps

1Step 1: Initialize counters for bulls and arrays for digit counts.
2Step 2: Loop through each digit in the guess and secret simultaneously to count bulls and track unmatched digits.
3Step 3: After counting bulls, calculate cows by summing the minimum counts of unmatched digits.

solution.py17 lines

1def getHint(secret, guess):
2    bulls = 0
3    cows = 0
4    secret_count = [0] * 10
5    guess_count = [0] * 10
6
7    for i in range(len(secret)):
8        if secret[i] == guess[i]:
9            bulls += 1
10        else:
11            secret_count[int(secret[i])] += 1
12            guess_count[int(guess[i])] += 1
13
14    for i in range(10):
15        cows += min(secret_count[i], guess_count[i])
16
17    return f'{bulls}A{cows}B'

ℹ

Complexity note: The time complexity is O(n) because we only loop through the strings once. The space complexity is O(n) due to the arrays used for counting digits, but since the size is constant (10), it can be considered O(1) in practical terms.

1Bulls are counted directly by comparing positions.
2Cows require counting unmatched digits to avoid double counting.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.