algoadvance

Leetcode 27. Remove Element

Problem Statement

Leetcode Problem 27: Remove Element

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. It doesn’t matter what you leave beyond the new length. Return the new length of the array after removing the specified elements.

Clarifying Questions

  1. Are we allowed to use additional space? No, the problem specifies that we need to do this in-place.

  2. What should we do if nums is empty? If nums is empty, the new length should be 0.

  3. Can val be any integer within the range of nums elements? Yes, val can be any integer.

  4. What if all elements in nums are the same and equal to val? The new length in this case should be 0.

  5. Are there any constraints on the size of the array or the value of integers? The constraints typically indicated in Leetcode are:

    • 0 <= nums.length <= 100
    • -50 <= nums[i], val <= 50

Strategy

We can solve this problem efficiently using the two-pointer technique:

  1. Pointer Initialization: Initialize two pointers, i and k.
    • k will traverse each element in the array.
    • i will track the position to place the elements that are not equal to val.
  2. Traversal and Placement:
    • Traverse the array using pointer k.
    • Whenever we encounter an element not equal to val, we place it at the i-th position and increment i.
  3. Return New Length: After the traversal, i will indicate the new length of the modified array, since all elements up to index i-1 are the elements that are not equal to val.

Time Complexity

Code

Here is the implementation in Java:

public class Solution {
    public int removeElement(int[] nums, int val) {
        int i = 0; // Pointer to place non-val elements
        for (int k = 0; k < nums.length; k++) {
            if (nums[k] != val) {
                nums[i] = nums[k];
                i++;
            }
        }
        return i;
    }
}

Explanation

  1. Initialization: Start with i = 0.
  2. Traversal:
    • Iterate through the array using k.
    • If nums[k] is not equal to val, set nums[i] = nums[k] and increment i.
  3. Result: The value of i at the end of the traversal is the new length of the array with the elements not equal to val.

This optimized approach ensures an in-place modification of the array with O(n) time complexity and O(1) space complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI