Find the First Occurrence of a Value
Solve this ProblemEasy5 min
Topics
BasicsArraysSearching
Companies
TCSInfosysWipro
Given an array
nums (which may contain repeated values) and a target, return the index of the target's first (leftmost) occurrence, or -1 if it does not appear.
With duplicates, "where is it?" has several answers, so the question must say which one. The scan directionScan DirectionWhether a loop walks from the first index up or from the last index down — it decides which match is met first. decides which match is seen first: scanning from the left finds the first occurrence immediately, while scanning from the right has to go all the way through.
Test Case 1:
Input:nums = [4, 9, 2, 9, 9], target = 9
Output:1
Explanation:9 appears at indexes 1, 3 and 4; the first is 1.
Test Case 2:
Input:nums = [4, 9, 2], target = 7
Output:-1
Explanation:Not present.
Constraints
- ◆
1 ≤ nums.length ≤ 1000 - ◆
-1000000 ≤ nums[i], target ≤ 1000000
Try the Dry Run
Approach & Solutions
Scan from the Right, Keep OverwritingGood
Walk from the last index down to 0 and, every time the target is seen, record that index. Because later records overwrite earlier ones and the walk ends at the front, the index left at the end is the leftmost one. It always scans the whole array.
Time
O(n)Space
O(1)Java
class Solution {
public int firstOccurrence(int[] nums, int target) {
int result = -1;
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[i] == target) {
result = i;
}
}
return result;
}
}Scan from the Left, Stop at the First MatchOptimal
Walk from index 0 upward and return immediately at the first match. The first match met from the left is by definition the first occurrence, and every element after it is skipped. Return −1 if the loop finishes.
Time
O(n)Space
O(1)Java
class Solution {
public int firstOccurrence(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
return i;
}
}
return -1;
}
}