My c++ solution with loop invariant, O(n), no extra space


  • 0
    C
    class Solution {
    public:
        int removeElement(vector<int>& nums, int val)
        {
            // nonval... unknown............... val...
            //           lo_unknown  hi_unknown 
            
            int lo_unknown = 0;
            int hi_unknown = nums.size()-1;
            
            while(lo_unknown <= hi_unknown)
            {
                if(nums[lo_unknown] == val)
                {
                    nums[lo_unknown] = nums[hi_unknown];
                    nums[hi_unknown--] = val;
                }
                else
                    lo_unknown++;
            }
            
            return hi_unknown+1;
        }
    };

Log in to reply
 

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