Two Java solutions (w and w/o extra memory)


  • 0

    Without Extra memory. The main idea is that, since order doesn't matter, we can keep two iterators i and length, where i starts at head and length starts at tail. We can then just increment i and iterate through through the array. If we encounter the marked value val we can just replace it with the value at tail index length, and make tail index val. When head index and tail index meets, we end the loop and return the length of the array.

    public class Solution {
        public int removeElement(int[] nums, int val) {
            if (nums.length == 0) return 0;
            int length = nums.length;
            int i = 0;
            while(i < length) {
                if (nums[i] == val && nums[length - 1] != val) {
                    nums[i] = nums[length - 1];
                    nums[length - 1] = val;
                } else if (nums[i] == val && nums[length - 1] == val) {
                    length -= 1;
                } else {
                    i += 1;
                }
            }
            return length;
        }
    }
    

    The solution with extra memory is pretty straight forward. We just compile an extra layer of masked array and iterate through the original nums array again and find the length.

    public class Solution {
        public int removeElement(int[] nums, int val) {
            if (nums.length == 0) return 0;
            
            int[] mask = new int[nums.length];
            for(int i = 0; i < nums.length; i++) {
                if (nums[i] == val) mask[i] = 1;
            }
            int fast = 0;
            int length = nums.length;
            int i = 0;
            while(fast < nums.length) {
                if (mask[fast] != 1) {
                    nums[i] = nums[fast];
                    fast += 1;
                    i += 1;
                } else {
                    fast += 1;
                    length -= 1;
                }
            }
            return length;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.