Find Transition Point — Easy Problem & Solution

You are given a sorted array arr that contains only 0s followed by only 1s. The transition point is the index of the first 1.

Difficulty: Easy
Topics: Arrays, Binary Search
Asked at: TCS, Infosys, Capgemini
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a sorted array arr that contains only 0s followed by only 1s. The transition point is the index of the first 1.

Return that index, or -1 if the array holds no 1 at all.

Example 1

Input: arr = [0,0,0,1,1]
Output: 3
Explanation: Index 3 is the first 1.

Example 2

Input: arr = [0,0,0,0]
Output: -1
Explanation: No 1 exists.

Example 3

Input: arr = [1,1,1]
Output: 0

Constraints

1 <= arr.length <= 500000
arr[i] is 0 or 1
All 0s come before all 1s.

How to solve Find Transition Point

The array is a run of 0s followed by a run of 1s, so the predicate 'this element is 1' is monotone — false then true. That is exactly what binary search finds the boundary of.

Approach

Set lo = 0, hi = n - 1, ans = -1.
While lo <= hi, take mid. If arr[mid] == 1, record ans = mid and search left (hi = mid - 1).
Otherwise the first 1 must be to the right, so lo = mid + 1.
Return ans, which stays -1 when no 1 was ever seen.

Why it works

Each iteration halves the range while preserving the invariant that ans is the leftmost 1 found so far and everything left of lo is 0. When the range empties, no smaller index can hold a 1.

Complexity

Time — O(log n)
Space — O(1)

Pitfalls

Returning mid as soon as a 1 is found — that is a one, not necessarily the first one.
(lo + hi) / 2 can overflow in fixed-width languages on very large arrays; lo + (hi - lo) / 2 is the safe form.

Reference solution

Python

from typing import List

def transitionPoint(arr: List[int]) -> int:
    lo, hi, ans = 0, len(arr) - 1, -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == 1:
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return ans

JavaScript

var transitionPoint = function(arr) {
    var lo = 0, hi = arr.length - 1, ans = -1;
    while (lo <= hi) {
        var mid = lo + ((hi - lo) >> 1);
        if (arr[mid] === 1) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    return ans;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue