Remove Duplicates From Sorted Array (Leetcode Problem #26)
Java Solution for https://leetcode.com/problems/remove-duplicates-from-sorted-array/
Originally published at https://asyncq.com
Understanding Problem
- We have given integer array nums which are in increasing order. We need to remove duplicates from the nums array so that nums only contains unique element and relative order of the element should be preserved.
- We cannot use additional memory and need to perform all the operations on the input nums array.
- If our input array contains k duplicates then the initial n-k element should be the output and we can ignore elements beyond n-k in the input.
- For example
nums = [2,2,3]
output = [2,3,__]nums = [ 1,1,1,2,2,2,3,4,4]
output = [1,2,3,4,______]
| N-k | k |
- Judges will only compare the n-k elements for the solution and elements after n-k is ignored
My Thought About Solution
- My first thought about the solution is that we traverse each element in the array and check if the next element is the same as the current element, if yes then we can perform a shift operation on the element from the next element to the end array.
- We also keep a count of each occurrence of duplicates in the variable.
Pseudocode
1: record traversed element in count variable & duplicate in match variable;
2: traverse each record in loop
if( current_element == next_element)
then perform left arrayshift operation by 1
if( count == nums.length-1 )
then we have come to the end lets break the loop
increase the counted element
3: Return counted_elements-duplicates+1;
Solutions
Result
Our solution passes all the test cases and is accepted by leetcode but the runtime is not so good. it almost takes 150 ms to run the code. I think we can do better. In our current solution, our runtime is o(n²), because we are calling loop inside the loop, so we need to improve that. lets target o(n)
Solution #2
- When we traverse the input array and we encounter a duplicate we will replace it with
Integer.MAX_VALUE - Then we can sort the elements in the input array, by doing this we will preserver the order and push all the duplicates to the end of the input array.
- Now we just have to return the length of the input array - duplicate count as a result
Result
Our result passes all the test cases and runtime is much improved from 150 ms to 2 ms since runtime complexity is improved from O(n²) to O(nlogn) since java sorting takes O(nlogn) time.
But I observed that it only beats 28% of the Leetcode java solution, so I think i have more scope to improve. I think the O(n) solution exists.
Solution #3
- We optimize our solution to O(n) from O(nlogn). In this solution, we traverse each element in the input array and check if the next element is not the same as the current element. If it's true then we add that to the input array
- Why this logic works?
we keep the first element of the input array since the first element itself cannot be duplicated, and then start checking from the 2nd element and compare with the previous element. if it's the same as the previous then it is duplicate and we ignore it, but if it is not duplicate then we add it to the input array as the next element. - For example
nums = [1,1,2]first iteration
nums = [1,1,2] -> check if num[0] != num[1]
in our case num[0]=num[1] so we ignore element num[1]State of nums = [1,1,2]Second iteration
nums = [1,1,2] => check if num[0]=num[2]
in our case num[0] != num[2] , hence we can assign num[1]=num[2]
State of nums = [1,2,2]iteration finishedSince we dont care about element after nums.length-duplicate i.e 3-1 = 2 would be returned as output ,
Judge will only compare 2 elements from out modified input array.i.e nums = [1,2,_] and 3rd element will be ignored
Result
Our result this time improved a lot, the runtime is almost 0ms and we beat 100% of the java submission.
Conclusion
This Leetcode problem teaches us how to think and improve the runtime of the code, this is one of the key aspects in coding interviews since the interviewer always asks how we can improve our existing solutions, either runtime complexity or space complexity.
Let me know if you have some opinions on the solutions in the comment section!
Bonus
- If you want to upskill your coding interview game, you should definitely check out this bestseller course ( this is in Java )
Happy Leetcoding!
Let’s connect on LinkedIn
If you like this article, please check more @ https://asyncq.com/
