General notes

• if you split the array, its better to write them in order on piece of paper to have more clarity
• don't think of solving problem inplace until required
• befort submitting check
  1. are you returning correct output
  2. syntax errors

344 Reverse String

link

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Solution:

var reverseString = function (s) {
    let left = 0;
    let right = s.length - 1;
    while (left < right) {
        let temp = s[left]
        s[left] = s[right]
        s[right] = temp
        left++
        right--
    }
};

Insight:

• 🔄 Two pointer problem

subarray sum equals k

brute force

• find all subarrays starting at 0, then 1, then 2

using prefix sum

• we don't need curr and can calculate sum of subarray but how do reduce time complexity?

prefix sum nuance

• if sum is same at two indices, then sum of subarray between them is 0

3, 2, -1, -2, 3 3, 5, 4, 2, 5

643 Max avg Subarray

link

var findMaxAverage = function (nums, k) {
    let ans = 0
    let sum = 0
    for (let i = 0; i < k; i++) {
        sum += nums[i]
    }
    ans = sum
    for (let i = k; i < nums.length; i++) {
        sum += nums[i] - nums[i - k]
        ans = Math.max(sum, ans)
    }
    return ans / k
};

977 Squares of a Sorted Array

link

var sortedSquares = function(nums) {
    let left = 0
    let right = nums.length - 1
    let ans = []
    for (let i = nums.length - 1; i >= 0; i--) {
        let leftVal = nums[left] * nums[left]
        let rightVal = nums[right] * nums[right]
        if (leftVal < rightVal) {
            ans[i] = rightVal
            right--
        } else {
            ans[i] = leftVal
            left++
        }
    }
    return ans
};

nuances

• input was sorted

insight

• the large numbers are on edge. use 2 pointers to compare them
• you need to reduce search space, either from right or from left
• since we are working with larger numbers first, we will start writing the output array from back
• outer loop keeps track of answer array, actual pointers close in on the array
• 2 pointer problem with some interesting cases (outer loop should work according to answer)
• 🔄 Two Pointers
• 🔚 reverse fill the output

main trick

• reverse fill the output

1004 Max Consecutive Ones III

link

var longestOnes = function (nums, k) {
    let ans = 0
    let count = 0
    let left = 0
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === 0) {
            count++
        }

        if (count > k) {
            if (nums[left] === 0) {
                count--
            }
            left++
        }

        ans = Math.max(right - left + 1, ans)

    }
    return ans
};

1413 Minimum Value to Get Positive Step by Step Sum

var minStartValue = function (nums) {
    let curr = nums[0]
    let min = curr
    for (let i = 1; i < nums.length; i++) {
        curr += nums[i]
        min = Math.min(curr, min)
    }
    return min < 0 ? Math.abs(min) + 1 : 1
};

insight:

• 📋 Prefix sum problem

1480 Running sum of 1d Array

link

var runningSum = function (nums) {
    let sum = [nums[0]]
    for (let i = 1; i < nums.length; i++) {
        sum[i] = nums[i] + sum[i - 1]
    }
    return sum
};

insight:

• prefix sum

2090 K Radius Subarray Averages