LeetCode: Remove Element

Question

• https://leetcode.com/problems/remove-element
• Level: Easy
• Type: Binary Search or some kind of implementation

Core Logic

Intuitive Logic

• Intuitively, we can use iterate through vector, and remove corresponding elements
• Which 'Looks like' O(N) solution, but if we look at the vector.erase()'s time complexity, worst case would take O(N) for each single erase operation.
• Meaning, looping through vector takes O(N), and if we remove an element, that operation also takes O(N).
  • So in worst case[i.e vector with all 2's and removeTarget = 2], this Logic takes O(N^2) times.

Bit more optimized Logic && Algorithm

• This approach will try to make logic's time complexity to O(N*Log(N))
• First, sort array with ascending-order.
  • This takes O(N*Log(N)) in worst case.
• Use binary search to search target.[O(Log(N))]
  • If there are multiple targets, find range in this case.
• Remove Target Range
  • Worst case would be O(N)
• Done!

Code

class Solution {
public:
    
    void getStartRange(int& container, int middleIndex, int& target, vector<int>& nums) {
        container = -1;
        
        while (middleIndex >= 0) {
            if (nums[middleIndex] != target) {
                container = middleIndex+1;
                break;
            }
            middleIndex--;
        }
        
        if (container == -1) container = 0;
    }
    
    void getEndRange(int& container, int middleIndex, int& target, vector<int>& nums) {
        container = -1;
        
        while (middleIndex < nums.size()) {
            if (nums[middleIndex] != target) {
                container = middleIndex-1;
                break;
            }
            middleIndex++;
        }
        
        if (container == -1) container = nums.size()-1;
    }
    
    int removeElement(vector<int>& nums, int val) {
        if (nums.empty()) {
            return 0;
        }
        sort(nums.begin(), nums.end());
        
        int start = 0;
        int end = nums.size()-1;
        int middleIndex = (start + end) / 2;
        
        int eraseStart = -1;
        int eraseEnd = -1;
        
        while (start <= end) {
            middleIndex = (start + end) / 2;
            if (nums[middleIndex] < val) {
                // Right
                start = middleIndex+1;
            } else if (nums[middleIndex] > val) {
                // Left
                end = middleIndex-1;
            } else {
                // Same
                getStartRange(eraseStart, middleIndex, val, nums);
                getEndRange(eraseEnd, middleIndex, val, nums);
                break;
            }
        }
        
        if (eraseStart != -1 && eraseEnd != -1) {
            nums.erase(nums.begin()+eraseStart, nums.begin()+eraseEnd+1);
        }
        
        return nums.size();
    }
};

Submission