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 <= 500000arr[i] is 0 or 1All 0s come before all 1s.
Hints for Find Transition Point
Hint 1
A linear scan works but throws away the fact that the array is sorted.
Hint 2
Binary search for the boundary: when you land on a
1, the answer is at that index or to its left.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
- Set
lo = 0,hi = n - 1,ans = -1. - While
lo <= hi, takemid. Ifarr[mid] == 1, recordans = midand search left (hi = mid - 1). - Otherwise the first
1must be to the right, solo = mid + 1. - Return
ans, which stays-1when no1was 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
midas soon as a1is found — that is a one, not necessarily the first one. (lo + hi) / 2can overflow in fixed-width languages on very large arrays;lo + (hi - lo) / 2is 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 ansJava
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