Find the Last 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 last (rightmost) occurrence, or -1 if it does not appear.
This is the mirror image of finding the first occurrence. Scanning from the left, you only know a match is the last one after reaching the end; reversing the scanReverse IterationLooping from the last index down to the first, e.g. for (i = n − 1; i >= 0; i--). lets the search stop at the first match it meets.
Test Case 1:
Input:nums = [4, 9, 2, 9, 1], target = 9
Output:3
Explanation:9 appears at indexes 1 and 3; the last is 3.
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 Left, Keep OverwritingGood
Walk the array from the front and record the index every time the target appears. Each new match overwrites the previous record, so after the loop the record holds the rightmost match. The whole array is always scanned.
Time
O(n)Space
O(1)Java
class Solution {
public int lastOccurrence(int[] nums, int target) {
int result = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
result = i;
}
}
return result;
}
}Scan from the Right, Stop at the First MatchOptimal
Turn the problem around: walk from the last index down to 0 and return at the first match. Coming from the right, the first match met is the last occurrence, so everything to its left can be skipped.
Time
O(n)Space
O(1)Java
class Solution {
public int lastOccurrence(int[] nums, int target) {
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[i] == target) {
return i;
}
}
return -1;
}
}