703286. Last duplicate element in a sorted array
Basic
Last Duplicate Element in a Sorted Array
Slug: last-duplicate-element-in-a-sorted-array5539
Difficulty: Basic
Id: 703286
Topic Tags: Arrays, Data Structures
Company Tags: None
Summary
Given a sorted array of integers, find the last duplicate element. The input array is already sorted in ascending order.
Detailed Explanation
To solve this problem, we can iterate through the array and keep track of the current element and its previous occurrence. If we encounter an element that matches the current one, we update the previous occurrence and continue the iteration until we find a new element or reach the end of the array.
Here's the step-by-step breakdown:
- Initialize two variables:
prevto store the previous element andlast_duplicateto store the last duplicate element. - Iterate through the array:
- For each element, check if it matches the current one (
curr) or its previous occurrence (prev). - If it's a match, update
prevwith the current element and setlast_duplicateto the current element. - If it's not a match, reset
prevto the current element.
- For each element, check if it matches the current one (
- Return
last_duplicate.
The time complexity of this algorithm is O(n), where n is the length of the array, since we iterate through the array once. The space complexity is O(1), as we only use a constant amount of extra memory.
Optimized Solutions
Java
public int lastDuplicate(int[] arr) {
int prev = -1;
int last_duplicate = -1;
for (int curr : arr) {
if (curr == prev) {
last_duplicate = curr;
}
prev = curr;
}
return last_duplicate;
}