Jessie Yu's Blog
Leetcode 27. Remove Element

Photo by Ali Yasar isgoren on Unsplash

Leetcode 27. Remove Element

Two Pointers Technique

Jessie Yu's photo
Jessie Yu
·

2 min read

Table of contents

The Problem: Remove Element

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

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.

The Brute Force Approach

The brute force approach involves looping through the array to find elements equal to val, and then looping again to move the subsequent elements to the removed position.

 function removeElement (nums, val) {
    let k = nums.length;
    for (let i = 0; i < k; i++) {
        if (nums[i] === val) {
            for (let j = i + 1; j < k; j++) {
                nums[j - 1] = nums[j];
            }
            i--;
            k--;
        }
    }
    return k;
}

Time Complexity Analysis:

  • The brute force approach has a time complexity of O(n^2) due to nested loops, where n is the length of the nums array.

Optimizing with Two Pointers Technique:

To improve efficiency, we'll leverage the two pointers technique, specifically, two pointers moving in the same direction. This involves maintaining two pointers: one to indicate the position where non-target elements should be placed, and another to iterate through the array.

function removeElement (nums, val) {
    let position = 0;
    for (let pointer = 0; pointer < nums.length; pointer++) {
        if (nums[pointer] !== val) {
            nums[position++] = nums[pointer];
        }
    }
    return position;
}

Time Complexity Analysis:

  • The solution has a time complexity of O(n) as it iterates through the array once.

Application of Two Pointers Technique:

The two pointers technique finds applications in various problems, including:

  • Two Sum (Problem #1)

  • Three Sum (Problem #15)

  • Container With Most Water (Problem #11)

  • Trapping Rain Water (Problem #42)

  • Remove Duplicates from Sorted Array (Problem #26)

  • Squares of a Sorted Array (Problem #977)

Conclusion:

By employing the two pointers technique, we can efficiently solve array manipulation problems while maintaining optimal time complexity. This technique offers a versatile approach to solving various algorithmic challenges, enhancing performance, and improving the efficiency of array operations.

leetcodealgorithms