|
This post is completed by 3 users
|
Add to List |
520. Remove Duplicates in a given Sorted Array
Given a sorted array of integers, write a program to remove duplicates in-place by modifying the given array such that all unique integers will be at the beginning of the array, and do not worry about other indexes after the new length.
Example:
Given Input: [1, 1, 2, 3, 3] Output: [1, 2, 3, 3, 3] [Modified array: 1, 2, 3] Given Input: [1, 1, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6] Output: [1, 2, 3, 4, 5, 6, 4, 5, 5, 5, 5, 6] [Modified array: 1, 2, 3, 4, 5, 6]
Approach:
A naive approach would be to use Set, Iterate the given array and put entries into Set, this will store all the unique entries into Set, later iterate the set, and put the entries back into array starting from index 0.
Better Solution: Iterate the array and whenever there is a change in the element, store the current element (element before change) at the beginning of the array (Handle the index). To handle the edge cases, store the first element of the array at index 0, do index=1, and current = first element of the array.
Output:
Given Input: [1, 1, 2, 3, 3] Modified: [1, 2, 3, 3, 3] ------------------------------- Given Input: [1, 1, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6] Modified: [1, 2, 3, 4, 5, 6, 4, 5, 5, 5, 5, 6]