Problem

Given a binary array (only 1’s followed by 0’s), find the first index where 0 starts. If no 0 is present, report accordingly. If the array contains only 0’s, return the first index (0).

Examples

Example 1

1
2
3

Input: nums = [1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0]
Output: 10
Explanation: The first zero appears at index 10.

Example 2

1
2
3

Input: nums = [1,1,1]
Output: -1
Explanation: No zero is present in the array.

Example 3

1
2
3

Input: [0,0,0]
Output: 0
Explanation: All elements are zero, so the first index is 0.

Solution

Method 1 – Linear Scan

Intuition

Scan the array from left to right. The first time you see a 0 in nums, that’s the answer. If no 0 is found, report accordingly.

Approach

  1. Start from index 0 and iterate through the array nums.
  2. If you find a 0, return its index immediately.
  3. If you reach the end without finding a 0, report that the array does not have a 0.

Code

1
2
3
4
5
6
7
8
9

class Solution {
public:
  int findFirstZero(const std::vector<int>& arr) {
    for (int i = 0; i < arr.size(); ++i) {
      if (arr[i] == 0) return i;
    }
    return -1; // No zero present
  }
};
1
2
3
4
5
6
7
8

class Solution {
  public int findFirstZero(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] == 0) return i;
    }
    return -1; // No zero present
  }
}
1
2
3
4
5
6

class Solution:
  def find_first_zero(self, arr: list[int]) -> int:
    for i, val in enumerate(arr):
      if val == 0:
        return i
    return -1  # No zero present

Complexity

  • ⏰ Time complexity: O(n) — Must check each element in the worst case.
  • 🧺 Space complexity: O(1) — Only a few variables for iteration.

Method 2 – Binary Search

Intuition

Since the array nums is sorted (all 1s then all 0s), we can use binary search to find the transition point efficiently.

Approach

  1. Set left and right pointers to the start and end of the array nums.
  2. While left ≤ right:
  • Find mid index.
  • If nums[mid] == 0 and (mid == 0 or nums[mid-1] == 1), return mid.
  • If nums[mid] == 1, search right half (left = mid + 1).
  • If nums[mid] == 0 and nums[mid-1] == 0, search left half (right = mid - 1).
  1. If no 0 is found, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
  int findFirstZero(const std::vector<int>& arr) {
    int left = 0, right = arr.size() - 1, ans = -1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (arr[mid] == 0) {
        if (mid == 0 || arr[mid - 1] == 1) return mid;
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return -1;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
  public int findFirstZero(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (arr[mid] == 0) {
        if (mid == 0 || arr[mid - 1] == 1) return mid;
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return -1;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
  def find_first_zero(self, arr: list[int]) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
      mid = left + (right - left) // 2
      if arr[mid] == 0:
        if mid == 0 or arr[mid - 1] == 1:
          return mid
        right = mid - 1
      else:
        left = mid + 1
    return -1

Complexity

  • ⏰ Time complexity: O(log n) — Each step halves the search space.
  • 🧺 Space complexity: O(1) — Only a few pointers and variables.