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.
The idea is to first determine the number of bulls by comparing characters at the same position in both the secret and the guess. In the first pass over the strings, count all bulls and track unmatched characters using two separate frequency arrays. In the second pass, use the frequency arrays to compute the number of cows by checking the minimum frequency of each character in unmatched parts.
In this C solution, two integer arrays secretCount and guessCount are used to count how many times each digit appears in the unmatched parts of secret and guess. After counting bulls and populating these arrays in the first loop, the second loop calculates cows by summing the minimum of matched counts in secretCount and guessCount.
Time Complexity: O(n), Space Complexity: O(1), where n is the length of the secret or guess.
Instead of performing two separate passes, this method uses a hashmap (or dictionary) to update the unmatched digits' count as it checks for bulls and non-bulls in a single iteration over the inputs. It utilizes incremental checking for cows during the mismatched segments.
This C function uses a single-pass approach with an array used as a hashmap to track digits. When encountering a mismatch, it checks and updates the hashmap to calculate cows immediately.
Time Complexity: O(n), Space Complexity: O(1).
We create two counters, cnt1 and cnt2, to count the occurrence of each digit in the secret number and the friend's guess respectively. At the same time, we create a variable x to count the number of bulls.
Then we iterate through the secret number and the friend's guess. If the current digit is the same, we increment x by one. Otherwise, we increment the count of the current digit in the secret number and the friend's guess respectively.
Finally, we iterate through each digit in cnt1, take the minimum count of the current digit in cnt1 and cnt2, and add this minimum value to the variable y.
In the end, we return the values of x and y.
The time complexity is O(n), where n is the length of the secret number and the friend's guess. The space complexity is O(|\Sigma|), where |\Sigma| is the size of the character set. In this problem, the character set is digits, so |\Sigma| = 10.
| Approach | Complexity |
|---|---|
| Counting Bulls and Cows with Two Passes | Time Complexity: O(n), Space Complexity: O(1), where n is the length of the secret or guess. |
| Single Pass Hashmap Tracking | Time Complexity: O(n), Space Complexity: O(1). |
| Counting | — |
| 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 |
bulls and cows | bulls and cows leetcode | leetcode 299 | string • Naresh Gupta • 15,783 views views
Watch 9 more video solutions →Practice Bulls and Cows with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor