Remove Duplicates from Sorted Array

🏠 ⬅️ ➡️

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums be k, to get accepted, you need to do the following things:

  • Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
  • Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; }

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [1,1,2] Output: 2, nums = [1,2,_] Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4,_,_,_,_,_] Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -100 <= nums[i] <= 100
  • nums is sorted in non-decreasing order.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 3
    integer, dimension(n) :: nums
    integer :: k

    ! Examples from the problem statement
    nums(1) = 1
    nums(2) = 1
    nums(3) = 2
    call print_array('Example 1', nums)
    k = remove_duplicates(nums)
    call print_array('Example 1', nums, k)

    nums(1) = 0
    nums(2) = 0
    nums(3) = 1
    nums(4) = 1
    nums(5) = 1
    nums(6) = 2
    nums(7) = 2
    nums(8) = 3
    nums(9) = 3
    nums(10) = 4
    call print_array('Example 2', nums)
    k = remove_duplicates(nums)
    call print_array('Example 2', nums, k)

contains

    subroutine print_array(title, arr, k)
        character(len=*) :: title
        integer, dimension(:), intent(in) :: arr
        integer, intent(in), optional :: k

        write (*, '(A)') trim(title)
        if (present(k)) then
            write (*, '(*(I0, 1X))') arr(1:k)
        else
            write (*, '(*(I0, 1X))') arr
        end if
        write (*, *)
    end subroutine print_array

end program main

function remove_duplicates(nums) result(k)
    implicit none
    integer, dimension(:), intent(inout) :: nums
    integer :: k

    ! Custom judge
    ! int[] nums = [...]; // Input array
    ! int[] expectedNums = [...]; // The expected answer with correct length
    !
    ! int k = removeDuplicates(nums); // Calls your implementation
    !
    ! assert k == expectedNums.length;
    ! for (int i = 0; i < k; i++) {
    !     assert nums[i] == expectedNums[i];
    ! }

    ! Solution
    k = 1
    do i = 2, size(nums)
        if (nums(i) /= nums(k)) then
            k = k + 1
            nums(k) = nums(i)
        end if
    end do

end function remove_duplicates
❌ Compiled
❌ Executed
❌ Correct 
module remove_duplicates
implicit none
contains

function remove_duplicates_(nums) result(k)
integer, intent(inout) :: nums(:)
integer :: k

! Local variables
integer :: i, j, n

! Initialize variables
k = 1
n = size(nums)

! Loop through the array and remove duplicates
do i = 2, n
    if (nums(i) /= nums(i-1)) then
        k = k + 1
        nums(k) = nums(i)
    end if
end do

end function remove_duplicates_

end module remove_duplicates

program test_remove_duplicates
use remove_duplicates, only: remove_duplicates_
implicit none

! Test case 1
integer, parameter :: nums1(3) = [1, 1, 2]
integer, parameter :: expected_nums1(2) = [1, 2]
integer :: k1

! Test case 2
integer, parameter :: nums2(9) = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
integer, parameter :: expected_nums2(5) = [0, 1, 2, 3, 4]
integer :: k2

! Test case 3
integer, parameter :: nums3(0) = []
integer, parameter :: expected_nums3(0) = []
integer :: k3

! Test case 4
integer, parameter :: nums4(1) = [1]
integer, parameter :: expected_nums4(1) = [1]
integer :: k4

! Test case 5
integer, parameter :: nums5(2) = [1, 2]
integer, parameter :: expected_nums5(2) = [1, 2]
integer :: k5

! Test case 6
integer, parameter :: nums6(3) = [1, 2, 3]
integer, parameter :: expected_nums6(3) = [1, 2, 3]
integer :: k6

! Test case 7
integer, parameter :: nums7(4) = [1, 2, 2, 3]
integer, parameter :: expected_nums7(3) = [1, 2, 3]
integer :: k7

! Test case 8
integer, parameter :: nums8(5) = [1, 2, 2, 3, 3]
integer, parameter :: expected_nums8(3) = [1, 2, 3]
integer :: k8

! Test case 9
integer, parameter :: nums9(6) = [1, 2, 2, 3, 3, 4]
integer, parameter :: expected_nums9(4) = [1, 2, 3, 4]
integer :: k9

! Test case 10
integer, parameter :: nums10(7) = [1, 2, 2, 3, 3, 4, 4]
integer, parameter :: expected_nums10(4) = [1, 2, 3, 4]
integer :: k10

! Test case 11
integer, parameter :: nums11(8) = [1, 2, 2, 3, 3, 4, 4, 5]
integer, parameter :: expected_nums11(5) = [1, 2, 3, 4, 5]
integer :: k11

! Test case 12
integer, parameter :: nums12(9) = [1, 2, 2, 3, 3, 4, 4, 5, 5]
integer, parameter :: expected_nums12(5) = [1, 2, 3, 4, 5]
integer :: k12

! Test case 13
integer, parameter :: nums13(10) = [1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
integer, parameter :: expected_nums13(6) = [1, 2, 3, 4, 5, 6]
🌐 Data from online sources 
def removeDuplicates(nums):
    if not nums: return 0
    i = 0
    for j in range(1, len(nums)):
        if nums[j] != nums[i]:
            i += 1
            nums[i] = nums[j]
    return i + 1

We use two pointers `i` and `j`. `i` starts at the first element and `j` at the second. We go through the array with `j` and compare the elements at the two pointers. If they are different, it means we found a unique element, so we move `i` to the next position and copy the value from `j` to `i`. When we finish going through the array, the length of the unique part is `i+1`.
🌐 Data from online sources 
int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int i = 0;
    for (int j = 1; j < nums.size(); j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

We use two pointers `i` and `j`. `i` starts at the first element and `j` at the second. We go through the array with `j` and compare the elements at the two pointers. If they are different, it means we found a unique element, so we move `i` to the next position and copy the value from `j` to `i`. When we finish going through the array, the length of the unique part is `i+1`.