Last Occurrence of Target in Sorted Array
Problem Statement
Given a sorted array nums with duplicates and a target value, return the index of the last occurrence of the target. If the target is not found, return -1.
Example Test Cases
- Input:
nums = [1, 2, 3, 4, 4, 5], target = 4
Output: 4
- Input:
nums = [1, 1, 2, 3, 5, 6], target = 4
Output: -1
Approaches
Brute Force Approach
-
Idea: Traverse the array and track the index of the last occurrence of the target.
-
Steps:
- Iterate through each element in the array.
- If the current element is equal to the target, update the index.
- Return the last updated index or
-1 if the target is not found.
-
Time Complexity: O(n) where n is the length of the array.
-
Space Complexity: O(1) as it uses constant extra space.
-
Example Code:
- Dry Run:
Input:
nums = [1, 2, 3, 4, 4, 5], target = 4
low = 0, high = 5, mid = 2 → nums[2] < 4, move low = 3low = 3, mid = 4, nums[4] == 4, and nums[5] > 4, return 4.
Complexity Analysis
Brute Force Approach
- Time Complexity:
O(n)
- Space Complexity:
O(1)
Efficient Approach
- Time Complexity:
O(log n)
- Space Complexity:
O(1)
Conclusion
The brute force approach is simple but inefficient for large arrays. The binary search approach is more efficient with logarithmic time complexity for finding the last occurrence.