LeetCode - Array

Posted on | In ,

Record the Array topic algorithm problems.

0001. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

solution 1: Brute Force

1
2
3
4
5
6
7
8
9
const twoSum = (nums, target) => {
    for(let i = 0; i < nums.length; i++) {
        for (let j = i+1; j < nums.length; j++) {
            if(nums[i] + nums[j] === target) {
                return [i,j]
            }
        }
    }
}

Runtime: 112 ms
Memory Usage: 34.9 MB

solution 2: Hash

1
2
3
4
5
6
7
8
9
const twoSum = (nums, target) => {
    let hash = {}
    for(let i = 0; i < nums.length; i++) {
        if (hash[target-nums[i]] !== undefined)
            return [hash[target-nums[i]],i];
        else
            hash[nums[i]] = i;
    }
}

Runtime: 60 ms
Memory Usage: 34.7 MB

solution 3: Map

1
2
3
4
5
6
7
8
9
10
const twoSum = (nums, target) => {
    const numsMap = new Map();
    for (let i = 0; i < nums.length; i++) {
        if(numsMap.has(target - nums[i]) ) {
            return [numsMap.get(target - nums[i]), i];
        } else {
            numsMap.set(nums[i], i);
        }
    }
}

Runtime: 56 ms
Memory Usage: 35.4 MB

0004. Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Follow up: The overall run time complexity should be O(log (m+n)).

Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Example 3:
Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000
Example 4:
Input: nums1 = [], nums2 = [1]
Output: 1.00000
Example 5:
Input: nums1 = [2], nums2 = []
Output: 2.00000

solution1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const findMedianSortedArrays = (nums1, nums2) => {
    let nums = nums1.concat(nums2);
    
    function quickSort(arr){
        if(arr.length<=1){return arr;}
        const pivotIndex=Math.floor(arr.length/2);
        const pivot=arr.splice(pivotIndex,1)[0];
        const left=[];
        const right=[];
        for(let i=0;i<arr.length;i++){
            if(arr[i]<=pivot){
                left.push(arr[i]);
            }else{
                right.push(arr[i]);
            }
        }
        return quickSort(left).concat([pivot],quickSort(right));
    }
    nums = quickSort(nums);   
    const numLength = nums.length;    
    if(numLength % 2 === 0){
        let len = numLength/2;
        return (nums[len-1]+nums[len])/2;
    }else{
        let len1 = (numLength/2)-0.5;
        return nums[len1];
    }
    
};

Runtime: 188 ms
Memory Usage: 57.9 MB

solution2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const findMedianSortedArrays = (nums1, nums2) => {
    if(nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
    let x = nums1.length;
    let y = nums2.length;
    let low = 0, high = x;
    while(low <= high) {
        const partitionX = (high + low) >> 1;
        const partitionY = ((x + y + 1) >> 1) - partitionX;
        
        const maxX = partitionX == 0 ? Number.NEGATIVE_INFINITY : nums1[partitionX - 1];
        const maxY = partitionY == 0 ? Number.NEGATIVE_INFINITY : nums2[partitionY - 1];
        
        const minX = partitionX == nums1.length ? Number.POSITIVE_INFINITY : nums1[partitionX];
        const minY = partitionY == nums2.length ? Number.POSITIVE_INFINITY : nums2[partitionY];
        
        if(maxX <= minY && maxY <= minX) {
            const lowMax = Math.max(maxX, maxY);
            if( (x + y) % 2 == 1) return lowMax;
            return (lowMax + Math.min(minX, minY)) / 2;
        } else if(maxX < minY) {
            low = partitionX + 1;
        } else 
            high = partitionX - 1;
    }  
};

Runtime: 132 ms
Memory Usage: 43.3 MB

solution3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const findMedianSortedArrays = (nums1, nums2) => {
    let totalLen = nums1.length + nums2.length;
  let idx1 = 0;
  let idx2 = 0;
  let curr;
  let last;

  while (idx1 + idx2 <= totalLen/2) {
    if (curr !== undefined) {
      last = curr;
    }
    let elOne = nums1[idx1];
    let elTwo = nums2[idx2];
    if (elOne === undefined) {
      curr = elTwo;
      idx2++;
    } else if (elTwo === undefined) {
      curr = elOne;
      idx1++;
    } else if (elOne < elTwo) {
      curr = elOne;
      idx1++;
    } else {
      curr = elTwo;
      idx2++;
    }
  }
  return totalLen % 2 === 0 ? (last + curr) / 2 : curr; 
};

Runtime: 144 m
Memory Usage: 43.3 MB

0011. Container With Most Water

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.

Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const maxArea = (height) => {
    let maxArea = 0;
    let start = 0, end = height.length - 1;
    while (end - start > 0){
        var area = Math.min(height[start], height[end]) * (end - start);
        maxArea = Math.max(maxArea, area);
        if (height[start] > height[end]){
            end--;
        } else {
            start++;
        }
    }
    return maxArea;
};

Runtime: 56 ms
Memory Usage: 35.7 MB

0015. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const threeSum = (nums) => {
    const results = [];
    if (nums.length < 3) {
        return results;
    }
    nums = nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length - 2; i++) {
        if (nums[i] > 0) {
            break;
        }
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        let j = i + 1;
        let k = nums.length - 1;
        while (j < k) {
            let sum = nums[i] + nums[j] + nums[k];
            if (sum === 0) {
                results.push([nums[i], nums[j], nums[k]]);
                while (nums[j] === nums[j + 1]) {
                    j++;
                }
                while (nums[k] === nums[k - 1]) {
                    k--;
                }
                j++;
                k--;
            } else if (sum < 0) {
                j++;
            } else {
                k--;
            }
        }
    }
    return results;
};

Runtime: 152 ms
Memory Usage: 46.5 MB

0026. Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn’t matter what you leave beyond the returned length.
Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn’t matter what values are set beyond the returned length.

solution 1

1
2
3
4
5
6
7
8
9
const removeDuplicates = (nums) => {
    for(let i = 0; i < nums.length; i++) {
        if(nums.indexOf(nums[i]) !== i) {
            nums.splice(i,1);
            i--;
        }
    }
    return nums.length
};

Runtime: 204 ms
Memory Usage: 37.5 MB

solution 2

1
2
3
4
5
6
7
8
const removeDuplicates = (nums) => {
    nums.forEach((n, index) => {
        while(n == nums[index +1]){
            nums.splice(index +1, 1);
        }
     });
    return nums.length;
};

Runtime: 92 ms
Memory Usage: 37.5 MB

solution 3

1
2
3
4
5
6
7
8
9
10
11
12
const removeDuplicates = (nums) => {
    let firstP = 0,
        secondP = 0;
    while(secondP < nums.length){
        if(nums[secondP] > nums[firstP]){
            firstP++;
            nums[firstP] = nums[secondP];
        }
        secondP++;
    }
    return firstP + 1;
};

Runtime: 60 ms
Memory Usage: 36.6 MB

0031. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const nextPermutation = (nums) => {
    const len = nums.length;
    // find the first descending element nums[i-1]
    let i = len - 1;
    while (i > 0) {
        if (nums[i-1] >= nums[i]) {
            i--;
        } else {
            break;
        }
    }
    // swap nums[i-1] with the smallest element between nums[i] and nums[length-1] that is larger than nums[i-1]
	let j = len - 1;
    while (j > i) {
        if (nums[j] <= nums[i-1]) {
            j--;
        } else {
            break;
        }
    }
    if (i !== 0) {
        [nums[i-1],nums[j]] = [nums[j],nums[i-1]]
    }
	// reverse the part between nums[i] and nums[length-1]
	let mid = Math.floor((i+len)/2);
    for (let k = i; k < mid; k++) {
        [nums[k],nums[len - k + i - 1]] = [nums[len - k + i - 1],nums[k]]
    }
};

Runtime: 64 ms
Memory Usage: 35.4 MB

0033. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const search = (nums, target) => {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            return mid;
        }
        // When dividing the roated array into two halves, one must be sorted.
        if (nums[left] <= nums[mid]) {
            // left is sorted
            if (nums[left] <= target && target <= nums[mid]) {
                // target is in this side
                right = mid - 1;
            } else {
                // target is in the other side
                left = mid + 1;
            }
        } else {
            // right is sorted
            if (nums[mid] <= target && target <= nums[right]) {
                // target is in this side
                left = mid + 1;
            } else {
                // target is in the other side
                right = mid - 1;
            }
        }
    }
    return -1;
};

Runtime: 60 ms
Memory Usage: 34.1 MB

0034. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const searchRange = (nums, target) => {
  let res = [-1, -1];
  let l = 0;
  let r = nums.length - 1;
  // find the left
  while (l < r) {
    const mid = Math.floor((l + r) / 2);
    if (nums[mid] < target) {
        l = mid + 1;
    } else {
        r = mid;
    }
  }
  if (nums[l] !== target) {
      return res;
  } else {
      res[0] = l;
  }
  // find the right
  r = nums.length - 1;
  while (l < r) {
    const mid = Math.ceil((l + r) / 2);
    if (nums[mid] > target) {
        r = mid - 1;
    } else {
        l = mid;
    }
  }
  res[1] = r;
  return res;
};

Runtime: 60 ms
Memory Usage: 34.9 MB

0039. Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const combinationSum = (candidates, target) => {
    if (!candidates) {
        return [];
    }
    if (target === 0) {
        return [[]];
    }
    candidates.sort((a,b) => { return a - b});
    let result = [];
    let len = candidates.length;
    function find(t, p, i) {
        if (t === 0) {
            result.push(p);
            return;
        } else {
            while (i < len && t - candidates[i] >= 0) {
                find(t - candidates[i], [...p, candidates[i]], i)
                i++;
            }
        }
    }
    find (target, [], 0);
    return result;
};

Runtime: 80 ms
Memory Usage: 37.4 MB

0041. First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:
Input: [1,2,0]
Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1
Follow up:
Your algorithm should run in O(n) time and uses constant extra space.

solution1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const firstMissingPositive = arr => {
    arr = arr.filter(v => v > 0)
    for (let i = 0; i <= arr.length; i++) {
        let currValue = Math.abs(arr[i]);
        if (arr[currValue - 1] > 0)
            arr[currValue - 1] *= -1;
    }
    for (let i = 0; i < arr.length; i++) {
        let currentElement = arr[i];
        
        if (currentElement > 0)
            return i + 1;
    }    
    return arr.length + 1; 
};

Runtime: 84 ms
Memory Usage: 38.9 MB

solution2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const firstMissingPositive = nums => {
    let missing = nums.length + 1;
    const rearrangeElementAsPerIndex = () => {
        let i = 0;
        while(i < nums.length){
            let current = nums[i];
            let proposedIndex = current - 1;

            if(current > 0 && current < missing && nums[proposedIndex] !== current)
                [nums[proposedIndex], nums[i]] = [nums[i], nums[proposedIndex]];
            else
                i++;
        }
    }
    
    const findFirstMissing = () => {
        let i = 1;
        while(i < missing && nums[i-1] === i) i++;
        missing = Math.min(missing, i);
    }
    
    rearrangeElementAsPerIndex();
    
    findFirstMissing();
    
    return missing;
};

Runtime: 72 ms
Memory Usage: 38.9 MB

0042. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

solution1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const trap = (height) => {
    let landArea = 0;
    let maxFromLeft = 0;
    let maxAreaFromLeft = 0;
    
    for (let h of height) {
        landArea += h;
        maxFromLeft = Math.max(maxFromLeft, h);
        maxAreaFromLeft += maxFromLeft;
    }
    
    let maxFromRight = 0;
    let maxAreaFromRight = 0;
    
    for (let i = height.length - 1; i >= 0; i--) {
        maxFromRight = Math.max(maxFromRight, height[i]);
        maxAreaFromRight += maxFromRight;
    }
    
    const boundingArea = height.length * maxFromLeft;
    const leftVoid = boundingArea - maxAreaFromLeft;
    const rightVoid = boundingArea - maxAreaFromRight;
    return boundingArea - leftVoid - rightVoid - landArea;
};

Runtime: 88 ms
Memory Usage: 40 MB

solution2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const trap = (height) => {
    let left = 0;
    let right = height.length-1;
    let leftMax = 0;
    let rightMax = 0;
    let ans = 0;
    while (left < right) {
        leftMax = Math.max(height[left], leftMax);
        if (leftMax > height[left]) {
            ans+= (leftMax - height[left]);
        }
        rightMax = Math.max(height[right], rightMax);
        if (rightMax > height[right]) {
            ans += (rightMax - height[right]);
        }
        height[left] < height[right] ? left++ : right--;
    }
    return ans;
};

Runtime: 84 ms
Memory Usage: 39.3 MB

0045. Jump Game II

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
You can assume that you can always reach the last index.

Example 1:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [2,3,0,1,4]
Output: 2

solution1:

1
2
3
4
5
6
7
8
9
10
11
12
13
const jump = (nums) => {
    let newMax = 0;
    let jump = 0;
    let oldMax = 0;
    for (let i=0;i<nums.length-1;i++) {
        newMax = Math.max(newMax, i+nums[i]);
        if (i == oldMax) {
            jump++;
            oldMax = newMax;
        }
    }
    return jump;
};

Runtime: 84 ms
Memory Usage: 39.9 MB

solution2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const jump = (nums) => {
    let newMax = 0;
    let jump = 0;
    let oldMax = 0;
    nums.some((v, i) => {
        if (oldMax >= nums.length - 1) {
            return true;
        }
        newMax = Math.max(i + v, newMax);       
        if (i === oldMax) {
            oldMax = newMax;
            jump++;
        }
    });
    return jump;
};

Runtime: 80 ms
Memory Usage: 40 MB

0048. Rotate Image

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Example 2:
Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

solution:

1
2
3
4
5
6
7
8
9
10
11
12

const rotate = (matrix) => {
    // reverse up to down
    matrix = matrix.reverse()
    for(let i in matrix) {
        for(let j = 0; j < i; j++) {
            // swap the symmetry
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]
        }
    }
    return matrix
};

Runtime: 64 ms
Memory Usage: 34 MB

0053. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

solution:

1
2
3
4
5
6
const maxSubArray = (nums) => {
    for (let i = 1; i < nums.length; i++){
        nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
    }
    return Math.max(...nums);
};

Runtime: 68 ms
Memory Usage: 35.5 MB

0055. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.

solution 1:

1
2
3
4
5
6
7
8
9
10
const canJump = (nums) => {
    let max = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (max < i) {
            return false;
        }
        max = Math.max(nums[i] + i, max);
    }
    return true;
};

Runtime: 60 ms
Memory Usage: 35.8 MB

solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const canJump = (nums) => {
    let idx = 0;
    let max = 0;
    let len = nums.length;
    while(idx < len) {
        max = Math.max(max, idx + nums[idx]);
        if (max >= len - 1) {
            return true;
        }
        if (max <= idx && nums[idx] === 0) {
            return false;
        }
        idx++;
    }
    return false;
};

Runtime: 52 ms
Memory Usage: 35.8 MB

0056. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const merge = (intervals) => {
    if (!intervals.length) {
        return intervals;
    }
    intervals.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
    let prev = intervals[0];
    let res = [prev];
    for (let curr of intervals) {
        if (curr[0] <= prev[1]) {
          prev[1] = Math.max(prev[1], curr[1]);
        } else {
          res.push(curr);
          prev = curr;
        }
    }
    return res;
};

Runtime: 72 ms
Memory Usage: 37.1 MB

0066. Plus One

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Example 2:
Input:[6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,3]
Output:[6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,4]
Explanation: The array represents the integer 6145390195186705543.

solution 1:

1
2
3
4
5
6
7
8
9
10
11
const plusOne = (digits) => {
    for(let i = digits.length - 1; i >= 0; i --){
        if(digits[i] === 9){
          digits[i] = 0;
        } else {
          digits[i]++;
          return digits;
        }
    }
    return [1, ...digits];
};

Runtime: 60 ms
Memory Usage: 33.7 MB

solution 2:

1
2
3
const plusOne = (digits) => {
    return String(BigInt(digits.join('')) + 1n).split('');
};

Runtime: 48 ms
Memory Usage: 33.8 MB

0075. Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library’s sort function for this problem.
Example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
Could you come up with a one-pass algorithm using only constant space?

solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const sortColors = (nums) => {
    let count0 = 0;
    let count1 = 0;
    let count2 = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 0) {
            count0++;
        } else if (nums[i] === 1) {
            count1++;
        } else {
            count2++;
        }
    }
    for (let i = 0; i < nums.length; i++) {
        if (i < count0) {
            nums[i] = 0;
        } else if (i < count0 + count1) {
            nums[i] = 1;
        } else {
            nums[i] = 2;
        }
    }
    return nums;
};

Runtime: 52 ms
Memory Usage: 33.8 MB

solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
const sortColors = (nums) => {
    let low = 0, high = nums.length - 1
    for (let i = 0; i <= high;i++) {
        if (nums[i] === 0) {
            [nums[i], nums[low]] = [nums[low], nums[i]]
            low++;
        } else if (nums[i] == 2) {
            [nums[i], nums[high]] = [nums[high], nums[i]]
            high--;
            i--;
        }
    }
};

Runtime: 48 ms
Memory Usage: 33.9 MB

0078. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

solution:

1
2
3
4
5
6
7
8
9
10
11
const subsets = (nums) => {
    let result = [];
    dfs([], 0);
    function dfs(current, index) {
        result.push(current);
        for(let i = index; i < nums.length; i++) {
            dfs(current.concat(nums[i]), i + 1);
        }
    }
    return result;
};

Runtime: 52 ms
Memory Usage: 34.9 MB

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:
board =
[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]
Given word = “ABCCED”, return true.
Given word = “SEE”, return true.
Given word = “ABCB”, return false.

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
const exist = (board, word) => {
    let wordLength = word.length;
    word = word.split("");

    function verify(row, col, matrix, path) {
        if(row < 0 || col < 0 || row >= matrix.length || col >= matrix[0].length || matrix[row][col] != word[path] || path > wordLength) {
            return false;
        }
        path++;
        matrix[row][col] = '#';
        if(path === wordLength) {
            return true;
        }
        if(verify(row - 1, col, matrix, path)) {
            return true;
        }
        if(verify(row, col + 1, matrix, path)) {
            return true;
        }
        if(verify(row + 1, col, matrix, path)) {
            return true;
        }
        if(verify(row, col - 1, matrix, path)) {
            return true;
        }
        matrix[row][col] = word[--path];
        return false;
    };

    for(let i = 0; i < board.length; i++) {
        for(let j = 0; j < board[i].length; j++) {
            if(verify(i, j, board, 0))
                return true;
        }
    }
    return false;
};

Runtime: 80 ms
Memory Usage: 38.1 MB

##0084. Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Example:
Input: [2,1,5,6,2,3]
Output: 10

solution1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const largestRectangleArea = (heights) => {
    let maxArea = 0;
    let currArea = 0;   
    for (let i = 0; i < heights.length; i++) {
        let l = i-1;                          
        let r = i+1;    
        let currHeight = heights[i];        
        // Since we are comparing out from the current element
        // elements of the same height as the current element 
        // will have the same max area rectangle.
        if (heights[r] === currHeight) continue;        
        currArea = currHeight;        
        // Check all bars to the left that are at least as tall.
        while (l >= 0 && heights[l] >= currHeight) {
            currArea += currHeight;
            l--;
        }        
        // Check all bars to the right that are at least as tall.
        while (r < heights.length && heights[r] >= currHeight) {
            currArea += currHeight;
            r++;
        }        
        maxArea = Math.max(currArea, maxArea);
        currArea = 0;
    }    
    return maxArea;
};

Runtime: 228 ms
Memory Usage: 39.3 MB

solution2:

largestRectangleArea 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  // Add a zero-height element 
  // so that we don't need to deal with last element of heights outside the for loop
  heights.push(0); 
  // so that stack always have an extra element, thus `stack[stack.length - 1]` is always valid
  let stack = [-1];
  let maxArea = 0; 
  for (let i = 0; i < heights.length; i++) {    
    let stackTopElement;    
    let minHeight = 0;    
    while ((stackTopElement = stack[stack.length - 1]) !== -1 && heights[i] < heights[stackTopElement]) {      
      stack.pop();      
      minHeight = heights[stackTopElement];      
      let count = i - stack[stack.length - 1] - 1;      
      maxArea = Math.max(maxArea, minHeight * count);      
    }
    stack.push(i);    
  }
  heights.pop();  
  return maxArea;
};

Runtime: 84 ms
Memory Usage: 41.9 MB

0088. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

solution 1:

1
2
3
4
5
6
7
const merge = function(nums1, m, nums2, n) {
    for(let i = m; i < nums1.length; i++ ){
       nums1[i] = nums2[i-m];
    }
    nums1.sort((a,b) => a > b ? 1 :-1);
    return nums1;
};

Runtime: 64 ms
Memory Usage: 35.1 MB

solution 2:

1
2
3
4
5
const merge = function(nums1, m, nums2, n) {
    const nums = nums1.slice(0, m).concat(nums2.slice(0, n));
    nums.sort((a, b) => a - b);
    nums.forEach((_n, i) => nums1[i] = _n);
};

Runtime: 60 ms
Memory Usage: 35 MB

solution 3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const merge = function(nums1, m, nums2, n) {
    let len = m + n;
    m--;
    n--;

    while (n >= 0) {
        len--;
        if (nums1[m] > nums2[n]) {
            nums1[len] = nums1[m--];
        } else {
            nums1[len] = nums2[n--];
        }
    }
};

Runtime: 52 ms
Memory Usage: 34 MB

0118. Pascal’s Triangle

Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
const generate = (numRows) => {
    if(!numRows) {
        return [];
    }
    let result = [[1]];
    for(let i = 1; i < numRows; i++) {
        result[i] = [];
        for(let j = 0; j < i + 1;j++) {
            result[i][j] = (result[i - 1][j - 1] || 0) + (result[i - 1][j] || 0) ;
        }
    }
    return result;
};

Runtime: 56 ms
Memory Usage: 33.8 MB

solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const generate = (numRows) => {
    if(!numRows) {
        return [];
    }
    let result = [[1]];
    for (let i = 1; i < numRows; i++) {
        const prevRow = result[result.length - 1];
        const shiftLeft = [...prevRow, 0];
        const shiftRight = [0, ...prevRow];

        const currentRow = shiftLeft.map((r, i) => r + shiftRight[i]);
        result.push(currentRow);
    }
    return result;
};

Runtime: 52 ms
Memory Usage: 33.6 MB

0121. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

solution 1:

1
2
3
4
5
6
7
8
const maxProfit = (prices) => {
    let maxCur = 0, maxSoFar = 0;
    for(let i = 1; i < prices.length; i++) {
        maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);
        maxSoFar = Math.max(maxCur, maxSoFar);
    }
    return maxSoFar;
};

Runtime: 52 ms
Memory Usage: 35.5 MB

Suppose we have original array:
[a0, a1, a2, a3, a4, a5, a6]
what we are given here is:
[b0, b1, b2, b3, b4, b5, b6]
where,b[i] = 0, when i == 0
b[i] = a[i] - a[i - 1], when i != 0
suppose if a2 and a6 are the points that give us the max difference (a2 < a6)
then in our given array, we need to find the sum of sub array from b3 to b6.
b3 = a3 - a2
b4 = a4 - a3
b5 = a5 - a4
b6 = a6 - a5
adding all these, all the middle terms will cancel out except two
b3 + b4 + b5 + b6 = a6 - a2
a6 - a2 is the required solution.
so we need to find the largest sub array sum to get the most profit

solution 2:

1
2
3
4
5
6
7
8
9
const maxProfit = (prices) => {
    let min = Number.MAX_SAFE_INTEGER;
    let max = 0;
    for (let i = 0; i < prices.length; i++) {
        min = Math.min(min, prices[i]);
        max = Math.max(max, prices[i] - min);
    }
    return max;
};

Runtime: 56 ms
Memory Usage: 35.5 MB

0122. Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

solution 1:

1
2
3
4
5
6
7
8
9
10
const maxProfit = (prices) => {
    if(!prices.length) {
        return 0;
    }
    let result = 0;
    for(let i = 1; i < prices.length; i++) {
        result += Math.max(0, prices[i] - prices[i-1]);
    }
    return result;
};

Runtime: 48 ms
Memory Usage: 35.7 MB

solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
const maxProfit = (prices) => {
    let diff = 0
    if (prices.length > 0) {
        prices.reduce((acc, next) => {
            if (next > acc) {
                diff += next - acc
            }
            return next
        })
    }
    return diff
};

Runtime: 60 ms
Memory Usage: 35.2 MB

0128. Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

Follow up: Could you implement the O(n) solution?

Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

soltution1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const longestConsecutive = (nums) => {
  if (nums == null || nums.length === 0) return 0;
  const set = new Set(nums);
  let max = 0;
  for (let num of set) {
    if (set.has(num - 1)) continue;  // make sure starting from the beginning of sequence
    let currNum = num;
    let currMax = 1;
    while (set.has(currNum + 1)) {
      currNum++;
      currMax++;
    }
    max = Math.max(max, currMax);
  }
  return max;
};

Runtime: 88 ms
Memory Usage: 41 MB

solution2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const longestConsecutive = (nums) => {
  let max = 0;
  const lens = {};
  for (let n of nums) {
    if (lens[n] != null) continue;
    const l = lens[n - 1] || 0;   // left length
    const r = lens[n + 1] || 0;   // right length
    const len = l + r + 1;
    // extend the length to the boundaries
    lens[n - l] = len;
    lens[n] = len;
    lens[n + r] = len;
    max = Math.max(max, len);
  }
  return max;
};

Runtime: 80 ms
Memory Usage: 41.2 MB

0169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2

solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const majorityElement = (nums) => {
    if (nums.length === 1) {
        return nums[0]
    }
    let count = {}
    for (let i = 0; i < nums.length; i++) {
        let num = nums[i]
        if (count[num] === undefined) {
            count[num] = 1;
        } else {
            count[num] += 1;
        }
    }
    let max = 0;
    let result = 0;
    for (let key in count) {
        if (count[key] > max) {
            max = count[key]
            result = key
        }
    }
    return result
};

Runtime: 68 ms
Memory Usage: 37.7 MB

solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const majorityElement = (nums) => {
    let len = nums.length;
    if (len === 1) {
        return nums[0]
    }
    let count = {}
    for (let i = 0; i < len; i++) {
        let num = nums[i]
        if (count[num] === undefined) {
            count[num] = 1;
        } else {
            count[num] += 1;
        }
        if (count[num] > len / 2) {
            return num;
        }
    }
};

Runtime: 60 ms
Memory Usage: 37.3 MB

solution 3:

1
2
3
4
5
6
7
8
9
const majorityElement = (nums) => {
    let len = nums.length;
    if (len === 1) {
        return nums[0]
    }
    // sort the array and the middle is the majority
    nums.sort((a,b) => a - b);
    return nums[Math.floor(len/2)];
};

Runtime: 76 ms
Memory Usage: 37.7 MB

0189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

solution 1:

1
2
3
4
5
6
7
const rotate = (nums, k) => {
    let x = 0
    while(x < k) {
        nums.unshift(nums.pop());
        x++;
    }
};

Runtime: 128 ms
Memory Usage: 35.3 MB

solution 2:

1
2
3
const rotate = (nums, k) => {
    nums.unshift(...nums.splice(nums.length - k));
};

Runtime: 60 ms
Memory Usage: 35 MB

0217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates.
Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
Example 1:
Input: [1,2,3,1]
Output: true
Example 2:
Input: [1,2,3,4]
Output: false
Example 3:
Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

solution 1:

1
2
3
const containsDuplicate = (nums) => {
    return (new Set(nums).size !== nums.length);
};

Runtime: 64 ms
Memory Usage: 40 MB

solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
const containsDuplicate = (nums) => {
    let obj = {};
    for(let i = 0; i < nums.length; i++){
        if (obj[nums[i]] === undefined) {
            obj[nums[i]] = 1;
        } else {
            return true;
        }
    }

    return false;
};

0238. Product of Array Except Self

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4]
Output: [24,12,8,6]
Note: Please solve it without division and in O(n).

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const productExceptSelf = (nums) => {
    let output = [];
    let leftMult = 1;
    let rightMult = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        output[i] = rightMult;
        rightMult *= nums[i];
    }
    for (let j = 0; j < nums.length; j++) {
        output[j] *= leftMult;
        leftMult *= nums[j];
    }
    return output;
};

Runtime: 88 ms
Memory Usage: 41.9 MB

0268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.
Example 1:
Input: [3,0,1]
Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8

solution 1:

1
2
3
4
5
6
7
8
9
const missingNumber = (nums) => {
    const n = nums.length;
    const expectedSum = (1 + n) * n / 2;
    let sum = 0;
    for(let i = 0; i < n; i++){
        sum += nums[i];
    }
    return expectedSum - sum;
};

Runtime: 128 ms
Memory Usage: 36.4 MB

solution 2:

1
2
3
4
5
6
7
8
const missingNumber = (nums) => {
    let sum = 0, total = 0
    for(let i = 0; i < nums.length; i++) {
        sum += nums[i]
        total += i + 1
    }
    return total - sum
};

Runtime: 80 ms
Memory Usage: 36.2 MB

solution 3:

1
2
3
4
5
const missingNumber = (nums) => {
    let sum = (nums.length * ( nums.length+1 ) ) / 2;
    let sum2 = nums.reduce((a, c) => a + c);
    return sum - sum2;
}

Runtime: 56 ms
Memory Usage: 35.8 MB

0283. Move Zeroes

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
Example:
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
const moveZeroes = (nums) => {
    let pointer = 0;
    for(let i = 0; i < nums.length; i++){
        if(nums[i] !== 0) {
            nums[pointer] = nums[i];
            pointer++;
        }
    }
    for(let j = pointer; j < nums.length; j++) {
        nums[j] = 0;
    }
};

Runtime: 56 ms
Memory Usage: 35.6 MB

solution 2:

1
2
3
4
5
6
7
8
const moveZeroes = (nums) => {
    for(let i = nums.length - 1; i >= 0; i--) {
        if(nums[i] === 0){
            nums.splice(i,1);
            nums.push(0);
        }
    }
};

Runtime: 76 ms
Memory Usage: 36.1 MB

0287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Example 1:
Input: [1,3,4,2,2]
Output: 2
Example 2:
Input: [3,1,3,4,2]
Output: 3

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const findDuplicate = (nums) => {
    if(nums.length === 1) {
        return nums;
    }
    const letterObj = {};
    for(let i = 0; i < nums.length; i++) {
        if(letterObj[nums[i]] === undefined) {
            letterObj[nums[i]] = 1;
        } else {
            letterObj[nums[i]]++;
        }

    }
    for(let key in letterObj) {
        if(letterObj[key] > 1) {
            return key
        }
    }
};

Runtime: 52 ms.
Memory Usage: 37.9 MB.

0448. Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]

solution 1:

1
2
3
4
5
6
7
8
9
10
const findDisappearedNumbers = (nums) => {
    let arr = []
    for (let i = 0; i < nums.length; i++) {
        arr[i] = i+1
    }
    for (v of nums) {
        arr[v-1] = -1
    }
    return arr.filter( i => (i > 0) )
};

Runtime: 176 ms
Memory Usage: 45.5 MB

solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const findDisappearedNumbers = (nums) => {
    for(let i = 0 ; i < nums.length; i++) {
        let val = nums[i];
        while(nums[val - 1] !== val) {
            [nums[val - 1] ,val] = [val, nums[val - 1]]
        }
    }
    let res = [];
    for(let i = 0 ; i < nums.length; i++ ){
        if(nums[i] !== i + 1) {
            res.push(i + 1);
        }
    }
    return res;
};

Runtime: 132 ms
Memory Usage: 43.9 MB

0560. Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
Input:nums = [1,1,1], k = 2
Output: 2
Note:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
const subarraySum = (nums, k) => {
    let counter = 0;
    for (let i = 0; i < nums.length; i++) {
        let base = 0;
        for (let j = i; j < nums.length; j++) {
            base += nums[j];
            if (base === k) {
                counter++;
            }
        }
    }
    return counter;
};

Runtime: 288 ms
Memory Usage: 35.8 MB

solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const subarraySum = (nums, k) => {
    let map = new Map();
    let sum = 0;
    let count = 0;
    map.set(0,1);
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (map.has(sum - k)) {
            count += map.get(sum - k);
        }
        if (map.has(sum)) {
            map.set(sum, map.get(sum) + 1);
        } else {
            map.set(sum, 1);
        }
    }
    return count;
};

Runtime: 88 ms
Memory Usage: 38.7 MB

0581. Shortest Unsorted Continuous Subarray

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.
You need to find the shortest such subarray and output its length.
Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const findUnsortedSubarray = (nums) => {
    const length = nums.length;
let min = nums[length-1];
let max = nums[0];
let l = 0;
    let r = length - 1;

for (let i = 1; i <= length - 2; i++)
{
if(nums[i] >= nums[i-1] && nums[i] >= nums[i+1]) {
            max = Math.max(max, nums[i]);
        }
if(nums[i] <= nums[i-1] && nums[i] <= nums[i+1]) {
            min = Math.min(min, nums[i]);
        }
}
while (nums[l] <= min) {
        l++;
    }
if(l === r + 1) {
        return 0
    }

while (nums[r] >= max) {
        r--;
    }
return r - l + 1;
};

Runtime: 68 ms
Memory Usage: 36.9 MB

0621. Task Scheduler

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.
However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.
You need to return the least number of intervals the CPU will take to finish all the given tasks.
Example:
Input: tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
Note:
The number of tasks is in the range [1, 10000].
The integer n is in the range [0, 100].

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const leastInterval = (tasks, n) => {
  if (n === 0) {
      return tasks.length;
  }
  let map = {};
  for (let key of tasks) {
    map[key] = map[key] ? map[key] + 1 : 1;
  }
  let max = 0, count = 0;
  Object.keys(map).forEach(key => {
    if (map[key] > max) {
      max = map[key];
      count = 1;
    } else if (map[key] === max) {
      count++;
    }
  })
  return Math.max((max-1)*(n+1) + count, tasks.length)
};

Runtime: 100 ms
Memory Usage: 41 MB

0912. Sort an Array

Given an array of integers nums, sort the array in ascending order.
Example 1:
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Example 2:
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

solution 1: Bubble

1
2
3
4
5
6
7
8
9
10
const sortArray = (nums) => {
    for(let i = 0; i < nums.length; i++) {
        for(let j = 0; j < nums.length - i -1; j ++) {
            if(nums[j] > nums[j + 1]){
                [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]]
            }
        }
    }
    return nums;
};

Runtime: 6624 ms
Memory Usage: 39.2 MB

solution 2: Selection

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const sortArray = (nums) => {
    const len = nums.length;
    for(let i = 0; i < len; i++) {
        let min = i;
        for(let j = i; j < len; j++) {
            if(nums[j] < nums[min]) {
                min = j;
            }
        }
        if(min !== i) {
            [nums[min], nums[i]] = [nums[i], nums[min]];
        }
    }
    return nums;
};

Runtime: 1360 ms
Memory Usage: 40.6 MB

solution 3: Insertion

1
2
3
4
5
6
7
8
9
10
11
12
const sortArray = (nums) => {
    for(let i = 1; i < nums.length; i++) {
        let key = nums[i];
        let j = i - 1;
        while ( nums[j] > key) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = key;
    }
    return nums;
};

Runtime: 5988 ms
Memory Usage: 39.2 MB

solution 4: Bisection

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const sortArray = (nums) => {
    for (let i = 1; i < nums.length; i++) {
        let key = nums[i], left = 0, right = i - 1;
        while (left <= right) {
            let middle = parseInt((left + right) / 2);
            if (key < nums[middle]) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        for (let j = i - 1; j >= left; j--) {
             nums[j + 1] = nums[j];
        }
        nums[left] = key;
    }
    return nums;
};

Runtime: 608 ms
Memory Usage: 42.6 MB

solution 5: Quick

sortArray 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    if(nums.length <= 1) {
        return nums;
    }
    let referValue = nums[0];
    let leftArr = [];
    let rightArr = [];
    for(let i = 1; i < nums.length; i++) {
        if(nums[i] < referValue) {
            leftArr.push(nums[i]);
        } else {
            rightArr.push(nums[i]);
        }
    }
    return sortArray(leftArr).concat([referValue], sortArray(rightArr));
};

Runtime: 116 ms
Memory Usage: 54.6 MB

solution 6: Shell

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const sortArray = (nums) => {
    const len = nums.length;
    let temp = 1, gap = 1;
    while(gap < len / 5) {
        gap =gap * 5 + 1;
    }
    for (gap; gap > 0; gap = Math.floor(gap / 5)) {
        for (let i = gap; i < len; i++) {
            temp = nums[i];
            for (var j = i - gap; j >= 0 && nums[j] > temp; j -= gap) {
                nums[j + gap] = nums[j];
            }
            nums[j + gap] = temp;
        }
    }
    return nums;
};

Runtime: 96 ms
Memory Usage: 40.5 MB