What Are Some of the Important Array Problems?

Tech-letter #14 | March 25, 2023

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. (The target will be the sum of two consecutive elements)

const twoSum = (nums, target) => {
    let numbers = []
    for (let i=0;i <nums.length; i++) {
        if(nums[i] + nums[i+1] === target) {
            numbers.push(i, i+1);
        }
    }
    return numbers;
};

2. Best time to BUY & SELL stock

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

const findMaxProfit = (prices) => {
    if (prices.length === 0) {
        return 0;
    }

    let minPrice = prices[0];
    let maxProfit = 0

    for (let i = 1; i < prices.length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i]
        } else {
             maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        }
    }
    return maxProfit;
}

3. Sliding window technique

• It involves dividing the data into fixed-size, overlapping segments, or “windows,” and performing a specific operation on each window.

• The technique is often used in problems that involve finding patterns or subarrays within a larger array, such as searching for a particular sequence of elements or calculating moving averages of a time series data.

If an array contains all non-negative integeres, the maximum subarray sum will be the sum of the entire array. Of course if the K is not specified.

What is a subarray?

• A subarray is a contiguous part of array, i.e., Subarray is an array that is inside another array.

An example of finding the maximum sum of a subarray of size k within a given array of integers.

For example, given the array: [1, 4, 2, 10, 2, 3, 1, 0, 20] and k=4, we want to find the maximum sum of any subarray of size 4 within the array.

1. We initialize two pointers, start and end, to the first and k-th elements of the array, respectively, and calculate the sum of the first subarray of size k.

   start = 0
   end = k - 1
   max_sum = sum(array[start:end+1])
   

2. We then iterate over the array from index k to the end, and slide the window one element to the right at each iteration. At each step, we calculate the sum of the current subarray and compare it with the current maximum sum. If the current sum is greater than the maximum sum, we update the maximum sum.

3. Return the maximum sum found.

It looks very simple. Let’s right a JS code for replicating the above algorithm.

function maxSubArraySum(arr) {
    let maxSum = 0;
    let currentSum = 0;
    const k = 4;

    for (let i = 0; i < k; i++) {
        currentSum += arr[i];
    }

    // at each iteration you need to move the window that is one element to the right
    for (let i = k; i < arr.length; i++>) {
        currentSum = currentSum - arr[i - k] + arr[i];
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

const arr = [1, 4, 2, 10, 2, 3, 1, 0, 20];
const result = maxSubArraySum(arr);
console.log(result);

Note: Using the divide and conquer to solve the maxuum sum of subarray

Divide and conquer technique may not be the most suitable approach for finding the maximum sum of a subarray of a fixed size. This is because divide and conquer techniques typically work by dividing the problem into smaller subproblems and solving them recursively. In the case of finding the maximum sum of a subarray of size k, there is no clear way to divide the problem into smaller subproblems. The sliding window technique is a more suitable approach for this problem, as it involves iterating over the array and sliding a window of fixed size k over it to calculate the maximum sum of any subarray of size k.

4. Other things that I learned this week

• You can’t simply import packages in vanilla javascript like you do in react or other libraries. Its silly, but you need to know.

• The fetch() won’t work in node versions that are below 18. The fetch() was working in the browser but failed in node. Sometimes, context switching is important, that is you need to understand where and how you are running your code.