Tome Voyage Validator 47 — Problem Statement & Solution Guide
Problem Description
You are given a non‑decreasing sequence of integers, indexed from 0. Your task is to locate the first element whose value equals its index plus one. If such an element does not exist, return -1. The input consists of a single array; the output is a single integer.
Input format:
- An array of integers nums.
Output format:
- The value of the first element satisfying nums[i] == i + 1, or -1 if none exists.
The array is guaranteed to be sorted in non‑decreasing order, which allows efficient search techniques.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Tome Voyage Validator 47"
WHY DOES IT MATTER?
Monotonic search patterns turn linear problems into logarithmic ones, a core skill for scaling solutions.
OPTIMIZATION CHALLENGE
The key is to exploit ordering to eliminate half the candidates each step, shrinking time from O(n) to O(log n).
REAL-WORLD CONNECTION
Think of locating the first defective product on an assembly line where defects only appear after a certain point.
Always verify the mid‑point condition and adjust bounds carefully to avoid infinite loops; a single off‑by‑one can break the search.
COMPLEXITY AT A GLANCE
O(log n)O(1)Core Theory — Why This Approach?
Because the array is sorted in non‑decreasing order, the relationship f(i)=nums[i]‑(i+1) is monotonic: if f(i) < 0 then for any j<i, f(j) ≤ f(i) < 0, and if f(i) > 0 then for any j>i, f(j) ≥ f(i) > 0. This monotonicity lets us apply binary search to locate the smallest index where nums[i] == i+1, achieving logarithmic time. A naïve linear scan checks each element, which is O(n) and becomes prohibitive for large inputs (e.g., n ≈ 10⁷) where time limits are tight. The optimal paradigm leverages the sorted property to prune half the search space at each step, reducing the worst‑case complexity from linear to logarithmic while using only O(1) extra space.
Interview Questions on This Problem
Q1Why can we treat nums[i]‑(i+1) as a monotonic function?
Because nums is non‑decreasing, increasing i never decreases nums[i]. Subtracting the strictly increasing term (i+1) preserves monotonicity. Hence the sign of the difference changes at most once.
Q2What is the advantage of binary search over a linear scan for this problem?
Binary search cuts the search space in half each iteration, giving O(log n) time versus O(n) for a scan. This matters when n is large or when the function is called repeatedly.
Q3How would you modify the algorithm if the array could contain duplicates and you needed the first occurrence?
After finding any match, continue searching the left half to ensure no earlier index also satisfies the condition. This is a classic lower‑bound binary search pattern.
Examples
Input
[1,2,3,4,5]
Output
1
Explanation: At index 0 the value is 1, and 0+1 equals 1. This is the earliest index that satisfies the condition, so the answer is 1.
Input
[0,2,3,4]
Output
2
Explanation: Index 0: 0≠1. Index 1: 2 equals 1+1, so the first matching element is 2.
Input
[2,3,4,5]
Output
-1
Explanation: Checking each index: 2≠1, 3≠2, 4≠3, 5≠4. No element matches, hence -1.
Input
[-1,0,1,2,3]
Output
-1
Explanation: All indices produce values that are one less than the required index+1; none match, so the result is -1.
Input
[1,1,1,1,1]
Output
1
Explanation: The first element at index 0 is 1, which equals 0+1. Therefore the answer is 1.
Constraints
- 1 <= nums.length <= 100000
- -1000000000 <= nums[i] <= 1000000000
- nums is sorted in non‑decreasing order
Optimal Approach & Strategy
Perform binary search on the sorted array, comparing nums[mid] with mid+1 and moving left or right based on the sign of the difference, tracking the smallest matching index.
Brute Force Approach
Iterate i from 0 to n‑1 and return i+1 when nums[i] == i+1; otherwise return -1 after the loop.
Verified Code Solutions
function solution(nums) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] === mid + 1) {
return mid;
} else if (nums[mid] < mid + 1) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}class Solution {
public:
int solution(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == mid + 1) {
return mid;
} else if (nums[mid] < mid + 1) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
};class Solution {
public int solution(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == mid + 1) {
return mid;
} else if (nums[mid] < mid + 1) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}def solution(nums):
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == mid + 1:
return mid
elif nums[mid] < mid + 1:
left = mid + 1
else:
right = mid - 1
return -1function solution(nums) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] === mid + 1) {
return mid;
} else if (nums[mid] < mid + 1) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.