Given an array of strings nums containing n unique binary strings each of length n, return a binary string of length n that does not appear in nums. If there are multiple answers, you may return any of them.
Example 1:
Input: nums = ["01","10"] Output: "11" Explanation: "11" does not appear in nums. "00" would also be correct.
Example 2:
Input: nums = ["00","01"] Output: "11" Explanation: "11" does not appear in nums. "10" would also be correct.
Example 3:
Input: nums = ["111","011","001"] Output: "101" Explanation: "101" does not appear in nums. "000", "010", "100", and "110" would also be correct.
Constraints:
n == nums.length1 <= n <= 16nums[i].length == nnums[i] is either '0' or '1'.nums are unique.Problem Overview: You receive n unique binary strings, each of length n. The goal is to construct another binary string of length n that does not appear in the list. Since there are 2^n possible binary strings but only n are provided, at least one valid answer must exist.
Approach 1: Backtracking with Hash Set (O(2^n * n) time, O(n) space)
Store all given strings in a hash set for constant‑time lookup. Then use backtracking to generate every possible binary string of length n. At each recursion step, append either '0' or '1' and continue until the string length reaches n. Once a candidate is built, check if it exists in the set. If it does not, return it immediately. The generation process explores up to 2^n possibilities and each membership check costs O(n) for string comparison, leading to O(2^n * n) time complexity. This method clearly demonstrates the search space and is easy to reason about, but it becomes inefficient for larger n.
Approach 2: Diagonal Construction (Cantor's Argument) (O(n) time, O(n) space)
The optimal approach uses a clever observation inspired by Cantor’s diagonalization. Look at the i-th string and flip its i-th bit: if it is '0', use '1'; otherwise use '0'. Append this flipped bit to your result string. After processing all n positions, the constructed string differs from the i-th input string at position i. That guarantees the result cannot match any string in the list. The algorithm only iterates once through the input array (array) and performs constant work per index, giving O(n) time and O(n) space for the output string. The approach relies purely on string manipulation and does not require extra data structures.
Recommended for interviews: Interviewers expect the diagonal construction solution. It shows you recognize the constraint that each string differs at a specific index, which eliminates the need to search the full space. Starting with the backtracking idea demonstrates understanding of the problem space, but moving to the O(n) diagonal solution shows strong algorithmic insight and familiarity with constructive proofs used in algorithm design.
This approach builds a unique binary string by considering each string's diagonal to ensure uniqueness. Specifically, we take advantage of the fact that flipping a bit diagonally guarantees that it differs from the original set of strings across at least one position. For each string at index i, we flip the character at the same index i, ensuring that the constructed string cannot match any existing strings due to its diagonal differentiation.
The Python solution generates a binary string by iterating over each index i of the strings in nums. At each index, it checks the diagonal bit nums[i][i] and inverts it. This results in a binary string that is guaranteed to be different from any given string in nums due to the difference along the diagonal.
Time Complexity: O(n) since we iterate through the array once.
Space Complexity: O(n) for storing the resulting binary string of length n.
This approach uses backtracking to generate all possible binary strings of length n and checks for the first one not present in nums. While not as efficient as diagonal construction, this method demonstrates a different strategy to ensure a solution's validity by exhaustive search.
The C# solution employs a backtracking method to explore every binary string possibility. If a binary string of the required length isn't in nums, it is identified as the result. The use of a recursive helper function facilitates generating possible candidates one bit at a time.
C#
JavaScript
Time Complexity: O(2^n) due to generating every binary string of length n.
Space Complexity: O(n) for the call stack during recursion.
Since the number of '1's in a binary string of length n can be 0, 1, 2, cdots, n (a total of n + 1 possibilities), we can always find a new binary string whose count of '1's differs from every string in nums.
We use an integer mask to record the counts of '1's across all strings, where the i-th bit of mask being 1 indicates that a binary string of length n with exactly i occurrences of '1' exists in nums, and 0 otherwise.
We then enumerate i starting from 0, representing the count of '1's in a binary string of length n. If the i-th bit of mask is 0, it means no binary string of length n with exactly i occurrences of '1' exists, and we can return that string as the answer.
The time complexity is O(L), where L is the total length of all strings in nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
C#
We can construct a binary string ans of length n, where the i-th bit of ans differs from the i-th bit of nums[i]. Since all strings in nums are distinct, ans will not appear in nums.
The time complexity is O(n), where n is the length of the strings in nums. Ignoring the space used by the answer string, the space complexity is O(1).
Java
C#
C++
JavaScript
Go
Python
TypeScript
| Approach | Complexity |
|---|---|
| Diagonal Construction Approach | Time Complexity: |
| Backtracking Approach | Time Complexity: |
| Counting + Enumeration | — |
| Construction | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Hash Set | O(2^n * n) | O(n) | Useful for understanding the full search space or when demonstrating recursive generation of binary strings |
| Diagonal Construction (Cantor's Argument) | O(n) | O(n) | Best approach for interviews and production; guarantees a unique string in linear time |
Find Unique Binary String - Leetcode Weekly Contest 1980 - Python • NeetCode • 20,022 views views
Watch 9 more video solutions →Practice Find Unique Binary String with our built-in code editor and test cases.
Practice on FleetCode