Watch 10 video solutions for Bulls and Cows, a medium level problem involving Hash Table, String, Counting. This walkthrough by Naresh Gupta has 14,913 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are playing the Bulls and Cows game with your friend.
You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:
Given the secret number secret and your friend's guess guess, return the hint for your friend's guess.
The hint should be formatted as "xAyB", where x is the number of bulls and y is the number of cows. Note that both secret and guess may contain duplicate digits.
Example 1:
Input: secret = "1807", guess = "7810" Output: "1A3B" Explanation: Bulls are connected with a '|' and cows are underlined: "1807" | "7810"
Example 2:
Input: secret = "1123", guess = "0111" Output: "1A1B" Explanation: Bulls are connected with a '|' and cows are underlined: "1123" "1123" | or | "0111" "0111" Note that only one of the two unmatched 1s is counted as a cow since the non-bull digits can only be rearranged to allow one 1 to be a bull.
Constraints:
1 <= secret.length, guess.length <= 1000secret.length == guess.lengthsecret and guess consist of digits only.Problem Overview: You receive two equal-length strings: secret and guess. A bull means the digit matches in both value and position. A cow means the digit exists in the secret but appears in a different position. The task is to compute counts for both and return them in the format xAyB.
Approach 1: Counting Bulls and Cows with Two Passes (O(n) time, O(1) space)
First iterate through both strings and count bulls directly by checking secret[i] == guess[i]. For digits that don't match, track their frequencies using two counting arrays of size 10 (since digits range from 0–9). After the first pass, run a second pass over the digit counts and sum the minimum frequency for each digit to compute cows. The key idea: unmatched digits from both strings contribute to cows if their counts overlap. This method avoids expensive searches and keeps memory constant. The approach relies on simple frequency counting, a common pattern in counting problems and string processing.
Approach 2: Single Pass Hashmap Tracking (O(n) time, O(1) space)
This version computes bulls and cows in a single traversal. Maintain a hash map (or array of size 10) that tracks the balance of digits seen in secret versus guess. When characters differ, increment the count for the secret digit and decrement for the guess digit. If a previously seen opposite imbalance exists (for example the guess digit appeared earlier in secret), that forms a cow. Each update checks whether the counter crosses zero to detect matches. The trick is that the map tracks surplus digits from both sides simultaneously, so cows are detected immediately without a second pass. This approach is compact and commonly used in interview solutions involving hash table frequency balancing.
Recommended for interviews: The single-pass hashmap approach is typically what interviewers expect because it shows you can track frequency differences while scanning once. The two-pass counting method is also acceptable and often easier to reason about during implementation. Mentioning both demonstrates strong problem-solving progression: brute logic first (count bulls, track digits), then optimization by merging the work into a single pass.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pass Counting | O(n) | O(1) | Best when clarity matters; easy to reason about using frequency arrays |
| Single Pass Hashmap Tracking | O(n) | O(1) | Preferred in interviews; computes bulls and cows simultaneously in one traversal |