Remove Element

🏠 ⬅️ ➡️

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val 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 elements which are not equal to val. 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 val = ...; // Value to remove int[] expectedNums = [...]; // The expected answer with correct length. // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length; sort(nums, 0, k); // Sort the first k elements of nums for (int i = 0; i < actualLength; i++) { assert nums[i] == expectedNums[i]; }

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

Example 1:

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

Example 2:

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

Constraints:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main

! This program solves the problem of removing all occurrences of a value in an integer array
! in place, without changing the order of the other elements.
!
! The problem statement is as follows:
!
! Given an integer array nums and an integer val, remove all occurrences of val in nums
! in-place. The relative order of the elements may be changed. Then return the new length
! of the array.
!
! Custom Judge:
!
! The judge will test your solution with the following code:
!
! int[] nums = [...]; // Input array
! int val = ...; // Value to remove
! int[] expectedNums = [...]; // The expected answer with correct length.
!                             // It is sorted with no values equaling val.
!
! int k = removeElement(nums, val); // Calls your implementation
!
! assert k == expectedNums.length;
! sort(nums, 0, k); // Sort the first k elements of nums
! for (int i = 0; i < actualLength; i++) {
!     assert nums[i] == expectedNums[i];
! }
!
! If all assertions pass, then your solution will be accepted.
!
! Examples:
!
! Example 1:
!
! Input: nums = [3,2,2,3], val = 3
! Output: 2, nums = [2,2,_,_]
! Explanation: Your function should return k = 2, with the first two elements of nums being 2.
!              It does not matter what you leave beyond the returned k (hence they are underscores).
!
! Example 2:
!
! Input: nums = [0,1,2,2,3,0,4,2], val = 2
! Output: 5, nums = [0,1,4,0,3,_,_,_]
! Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
!              Note that the five elements can be returned in any order.
!              It does not matter what you leave beyond the returned k (hence they are underscores).
!
! Constraints:
!
!     0 <= nums.length <= 100
!     0 <= nums[i] <= 50
!     0 <= val <= 100

implicit none

integer, parameter :: dp = selected_real_kind(15)

interface
    subroutine remove_element(nums, val) bind(c)
        use iso_c_binding
        implicit none
        integer(c_int), intent(inout) :: nums(*)
        integer(c_int), value :: val
    end subroutine
end interface

integer, allocatable :: nums(:)
integer :: val, k, i, j
character(len=100) :: line

! Read input from stdin
do while (.true.)
    read(unit=*, fmt='(A)', iostat=i) line
    if (i /= 0) exit
    backspace(unit=*)
    allocate(nums(size(line)))
    read(unit=*, fmt=*) nums
    call remove_element(nums, val)
    write(*, '(I0, X, *(I0, X))') k, nums(1:k)
    deallocate(nums)
end do

contains

subroutine remove_element(nums, val)
    implicit none
    integer, intent(inout) :: nums(*)
    integer, value :: val
    integer :: i, j

    ! Remove all occurrences of val in nums
    k = 0
    do i = 1, size(nums)
        if (nums(i) /= val) then
            k = k + 1
            nums(k) = nums(i)
        end if
    end do

    ! Return the new length of nums
    return
end subroutine

end program
❌ Compiled
❌ Executed
❌ Correct 
module remove_element
implicit none
contains

function remove_element(nums, val) result(k)
integer, intent(inout) :: nums(:)
integer, intent(in) :: val
integer :: k

! Local variables
integer :: i, j

! Initialize variables
k = 0
i = 1
j = 1

! Loop through the array and remove all occurrences of val
do while (i <= ubound(nums, 1))
    if (nums(i) /= val) then
        nums(j) = nums(i)
        j = j + 1
        k = k + 1
    end if
    i = i + 1
end do

! Sort the first k elements of nums
call sort(nums, 1, k)

end function remove_element

end module remove_element

program test_remove_element
use remove_element
implicit none

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

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

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

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

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

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

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

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

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

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

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

! Test
🌐 Data from online sources 
def removeElement(nums, val):
    i = 0
    for j in range(len(nums)):
        if nums[j] != val:
            nums[i] = nums[j]
            i += 1
    return i

The algorithm uses two pointers approach. The pointer i maintains the position where the next non-val element should be placed, and pointer j iterates through the array. If the element at j is not equal to val, we place it at the position i and increment the i pointer. The loop continues until we have checked all the elements in the array. The i pointer will give us the count of elements that are not equal to val, which is the result. Thus, we return the value of i as the final result.

The time complexity of this algorithm is O(n), where n is the number of elements in the array, as we only iterate through the array once. The space complexity is O(1) since we do not use any extra memory. We modify the input array in-place.

🌐 Data from online sources 
int removeElement(vector<int>& nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.size(); j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
}

The algorithm uses two pointers approach. The pointer i maintains the position where the next non-val element should be placed, and pointer j iterates through the array. If the element at j is not equal to val, we place it at the position i and increment the i pointer. The loop continues until we have checked all the elements in the array. The i pointer will give us the count of elements that are not equal to val, which is the result. Thus, we return the value of i as the final result.

The time complexity of this algorithm is O(n), where n is the number of elements in the array, as we only iterate through the array once. The space complexity is O(1) since we do not use any extra memory. We modify the input array in-place.