In this tutorial we will understand LeetCode Problem 1980 – Find Unique Binary String. This problem introduces a beautiful mathematical concept called the Cantor Diagonalization Trick.

By the end of this guide you will understand:

• Problem intuition
• Step-by-step visual explanation
• Pointer movement diagrams
• Optimal Java solution
• Alternative approaches
• Interview insights

--- ---

Problem Statement

You are given an array of n unique binary strings, each of length n. Return a binary string of length n that does not appear in the array.

Example

Input:
nums = ["01","10"]

Output:
"00" or "11"

There can be multiple correct answers. You only need to return one.

---

Understanding the Idea

For binary strings of length n there are:

2^n possible binary strings

But the array contains only:

n strings

So there must always exist **another unique string**. ---

Explanation

Take diagonal elements:

nums[0][0] = 0
nums[1][1] = 0

Flip them:

0 → 1
0 → 1

Construct new string:

11

This string **cannot match any string in the list**. ---

Pointer Movement

We move pointer i from 0 → n-1.

i = 0
nums[0][0] = 0
flip → 1

result = "1"

i = 1
nums[1][1] = 0
flip → 1

result = "11"

Final Answer:

"11"

---

Why This Works (Diagonal Trick)

We build a string that differs from:

• String 0 at position 0
• String 1 at position 1
• String 2 at position 2

Therefore the generated string **cannot equal any existing string**. This concept is known as: ---

Optimal Java Solution

class Solution {

    public String findDifferentBinaryString(String[] nums) {

        int n = nums.length;

        StringBuilder result = new StringBuilder();

        for(int i=0;i

---

Complexity Analysis

Time Complexity : O(n)

Space Complexity : O(n)


This is extremely efficient.

---

Other Possible Approaches

1. Brute Force

Generate all binary strings from:

0 → 2^n - 1


Check which string is missing.

Time Complexity:

O(2^n)


❌ Slow

---

2. Backtracking

Generate binary strings recursively.

Example:

generate("")
generate("0")
generate("1")


Complexity:

O(2^n)


---

Interview Tip

If you see:

✔ **n binary strings of length n**  
✔ **Find missing string**

Think immediately about:


Diagonal Construction Technique


---

Frequently Asked Questions

Is the answer always guaranteed?

Yes. Since there are 2^n possible strings but only n provided.

---

Why does the diagonal trick work?

Because the generated string differs from every string at least at one index.

---

Is this used in real algorithms?

Yes. It is derived from **Cantor’s diagonal argument in mathematics**.

---

Conclusion


LeetCode 1980 is a great example of combining mathematics and algorithms.
Instead of brute force, the diagonal trick gives us a linear time solution.



If you enjoy learning DSA problems explained visually,
check more tutorials on ExpertFunda.


---