Leetcode Stuff

leetcode.js

// Remove Element (3/11)
// https://leetcode.com/problems/remove-element/

// time o(n) | space o(1)
var removeElement = function(nums, val) {
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== val) {
      nums[count] = nums[i];
      count++;
    }
  }
  
  return count;
};



// Contains Duplicate 2 (3/11)
// https://leetcode.com/problems/contains-duplicate-ii/

// min(n,k) - extra space depends on set size
// which is size of the sliding window min(n,k)
// time o(n) | space o(min(n,k))
var containsNearbyDuplicate = function(nums, k) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (i - map.get(nums[i]) <= k) return true;
    map.set(nums[i], i);
  }
  
  return false;
};


// Max Average Sub Array (3/11)
// first loop goes from 0 to k
// we compute 
// second loop goes from k to nums.length
// we evict by substracting, then re-compute
var findMaxAverage = function(nums, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) {
    sum += nums[i];
  }
  
  let max = sum;
  for (let i = k; i < nums.length; i++) {
    sum -= nums[i - k];
    sum += nums[i];
    max = Math.max(sum, max);
  }
  
  return max / k;
};



// Moving Average From Data Stream (3/10)
// utilizes a circular queue, helping achieve o(n) instead of o(m) space complexity
// where m is len of queue which would grow at each invocation of the .next function
// and n is size of circular queue

// we initialize class with isFirstRound to true
// it won't be turned to false until we're back at currentIdx 0
// which will take this.size times (when we fill up)
// that's when we evict our item (subtracting from total)

// MISC CHALLENGE: make it work with fixed array size
// so constructor with this.array = new Array(size);
// challenge is if I use it, getAvg() gets screwed
// due to incorrect array.length

// time o(n) | space o(n)
class CircularQueue {
  constructor(size) {
    this.array = [];
    this.max = size;
    this.writehead = 0;
    this.sum = 0;
    this.isFirstRound = true;
  }
  
  push(value) {
    this.sum += value;
    
    if (!this.isFirstRound) {
      this.sum -= this.array[this.writehead];
    }
    
    this.array[this.writehead] = value;
    this.writehead = (this.writehead + 1) % this.max;
    
    if (this.writehead === 0) {
      this.isFirstRound = false;
    }
    
  }
  
  getAverage() {
    return this.sum / this.array.length;
  }
  
}

var MovingAverage = function(size) {
  this.queue = new CircularQueue(size);
};

MovingAverage.prototype.next = function(val) {
  this.queue.push(val);
  return this.queue.getAverage();
};



// Merge Sorted Arrays And Remove Duplicates (3/9)
// create a third array and two pointers
// if equal value, move p's together, else push smaller of two values and inc accordingly
// if there are remaining elements in arr1 or arr2, copy them as well
// no need for if conditions, just run 2 separate while loops
// reminder we'll be one idx over, so it's p < arr.length (not p < arr.length - 1)

// reminder
// first while loop expression1 && expression2, not ||
// because false || true is true and we need to be false and exit loop

// we must create a third array of size n+m
// time o(n+m) | space o(n+m)
function mergeSortedAndRemoveDup(arr1, arr2) {
  const merge = []
  let p1 = 0;
  let p2 = 0;
  while (p1 < arr1.length && p2 < arr2.length) {
    const curr1 = arr1[p1];
    const curr2 = arr2[p2];
    if (curr1 === curr2) {
      merge.push(curr1);
      p1++;
      p2++
    } else if (curr1 < curr2) {
      merge.push(curr1);
      p1++;
    } else {
      merge.push(curr2);
      p2++;
    }
  }
  
  while (p1 < arr1.length) {
    merge.push(arr1[p1]);
    p1++;
  }
  
  while (p2 < arr2.length) {
    merge.push(arr2[p2]);
    p2++;
  }
  
  return merge;
}

mergeSortedAndRemoveDup([0,3,4,5], [1,2,3])
mergeSortedAndRemoveDup([0,3,4,5,6,7,8,1003], [1,2,3,7,11,1002,3000])



// Remove Duplicates 2 (3/8)
// https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

// can leave two dups at most and get rid of rest
// array comes sorted in non-decreasing order

// if current value is same as arr[insertIdx - 2] 
// then you're now at more than your second duplicate
// so you want to throw this value away
// your insert index is like your writehead
// you don’t actually care what the value at your writehead is

// time o(n) | space o(1)
var removeDuplicates = function(nums) {
  let insertIdx = 2;
  for (let i = 2; i < nums.length; i++) {
    if (nums[insertIdx - 2] !== nums[i]) {
      nums[insertIdx] = nums[i];
      insertIdx++;
    }
  }
  
  return insertIdx;
};



// Remove Duplicates 1 (8/9)
// https://leetcode.com/problems/remove-duplicates-from-sorted-array/
// can leave no dups

// array is already sorted, so...
// use fast/slow pointers starting at idx 1
// if arr[fast - 1] isn't equal to arr[fast]
// then arr[slow] = arr[fast] and slow++
// regardless, remember to increment fast
// reminder! the comparison is fast and prev to fast

// time o(n) | space o(1)
var removeDuplicates = function(nums) {
  if (nums.length === 0) return 0;
  
  let slow = 1;
  let fast = 1;
  while (fast < nums.length) {
    if (nums[fast - 1] !== nums[fast]) {
      nums[slow] = nums[fast]
      slow++;
    }
    fast++;
  }
  
  return slow;
};