Scale Engineer

Bulls and Cows

Med
#0286Time: O(n^2), where `n` is the length of the strings. The first pass is `O(n)`, but the second pass involves nested loops, leading to `O(n^2)` in the worst case.Space: O(n), where `n` is the length of the strings. This is required to store the `secretUsed` and `guessUsed` boolean arrays.3 companies
Patterns
Counting
Data structures
Hash TableString
Companies
Epic SystemsZopsmartCARS24

Prompt

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:

  • The number of "bulls", which are digits in the guess that are in the correct position.
  • The number of "cows", which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.

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 <= 1000
  • secret.length == guess.length
  • secret and guess consist of digits only.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses two passes over the input strings. The first pass identifies and counts "bulls" (digits in the correct position). The second pass uses nested loops to find "cows" (correct digits in the wrong position) among the remaining characters. To avoid recounting, boolean flags are used to mark characters that have been matched as either a bull or a cow.

Algorithm

  • Initialize bulls and cows to 0.
  • Get the length n of the strings.
  • Create two boolean arrays, secretUsed and guessUsed, of size n, initialized to false.
  • First Pass (Bulls): Iterate from i = 0 to n-1. If secret.charAt(i) equals guess.charAt(i), increment bulls and set secretUsed[i] and guessUsed[i] to true.
  • Second Pass (Cows): Iterate through the guess string with index i. If guessUsed[i] is false, start an inner loop through the secret string with index j.
  • In the inner loop, if secretUsed[j] is false and guess.charAt(i) equals secret.charAt(j), we've found a cow. Increment cows, set secretUsed[j] to true, and break the inner loop to prevent matching the same secret character again.
  • Finally, format the result as a string: bulls + "A" + cows + "B".

Walkthrough

This method directly simulates the matching process. It first iterates through the strings to find all exact matches (bulls) and marks them as used. Then, it performs a second, nested iteration on the remaining, unused characters to find matches in wrong positions (cows). This ensures that a character is not counted as both a bull and a cow, and also that each character is used in at most one match.

class Solution {    public String getHint(String secret, String guess) {        int bulls = 0;        int cows = 0;        int n = secret.length();        boolean[] secretUsed = new boolean[n];        boolean[] guessUsed = new boolean[n];         // First pass for bulls        for (int i = 0; i < n; i++) {            if (secret.charAt(i) == guess.charAt(i)) {                bulls++;                secretUsed[i] = true;                guessUsed[i] = true;            }        }         // Second pass for cows        for (int i = 0; i < n; i++) {            if (guessUsed[i]) {                continue;            }            for (int j = 0; j < n; j++) {                if (!secretUsed[j] && secret.charAt(j) == guess.charAt(i)) {                    cows++;                    secretUsed[j] = true;                    break; // Found a match for guess[i], move to the next guess character                }            }        }         return bulls + "A" + cows + "B";    }}

Complexity

Time

O(n^2), where `n` is the length of the strings. The first pass is `O(n)`, but the second pass involves nested loops, leading to `O(n^2)` in the worst case.

Space

O(n), where `n` is the length of the strings. This is required to store the `secretUsed` and `guessUsed` boolean arrays.

Trade-offs

Pros

  • Simple to understand and implement.

  • The logic directly follows the problem definition.

Cons

  • Inefficient due to the O(n^2) time complexity, which can be slow for larger inputs.

  • Uses extra space proportional to the input size.

Solutions

class Solution { public String getHint ( String secret , String guess ) { int x = 0 , y = 0 ; int [] cnt1 = new int [ 10 ]; int [] cnt2 = new int [ 10 ]; for ( int i = 0 ; i < secret . length (); ++ i ) { int a = secret . charAt ( i ) - '0' , b = guess . charAt ( i ) - '0' ; if ( a == b ) { ++ x ; } else { ++ cnt1 [ a ]; ++ cnt2 [ b ]; } } for ( int i = 0 ; i < 10 ; ++ i ) { y += Math . min ( cnt1 [ i ], cnt2 [ i ]); } return String . format ( "%dA%dB" , x , y ); } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem