Find Transition Point

Easy
616.

Find Transition Point

Find Transition Point is an easy coding problem on arrays and binary search, asked in TCS, Infosys and Capgemini interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var transitionPoint = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Transition Point — Solution in Python, Java & C++

Find Transition Point solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find Transition Point is an easy coding problem on arrays and binary search, asked in TCS, Infosys and Capgemini interviews.

  • 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.

Hints for Find Transition Point

  1. Hint 1

    A linear scan works but throws away the fact that the array is sorted.

  2. Hint 2

    Binary search for the boundary: when you land on a 1, the answer is at that index or to its left.

  3. Hint 3

    Keep the best candidate seen so far and keep shrinking to the left half.

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

  1. Set lo = 0, hi = n - 1, ans = -1.
  2. While lo <= hi, take mid. If arr[mid] == 1, record ans = mid and search left (hi = mid - 1).
  3. Otherwise the first 1 must be to the right, so lo = mid + 1.
  4. 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

Java

public static int transitionPoint(int[] arr) {
    int lo = 0, hi = arr.length - 1, ans = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == 1) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    return ans;
}

C++

int transitionPoint(vector<int>& arr) {
    int lo = 0, hi = (int) arr.size() - 1, ans = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search