The minimum subarray problem with JavaScript

The minimum subarray problem with JavaScript

This problem can be compared to real-world scenarios where you want to minimize some negative outcome over a period of time or across sequential steps. Before diving in code, let's look at a couple real life examples where this algorithm may be useful.

Financial loss minimization

Imagine you're tracking the profit or loss of a business over time, say day by day. Positive numbers represent profit, and negative numbers represent losses. The goal is to identify the period (subarray of days) where the business experienced the worst financial performance.

For example, you have a business, and you're recording daily profit and loss data for each day of the month. To understand your business's worst period, you want to find the sequence of consecutive days where you lost the most money. The "Minimum Subarray" in this case would represent the consecutive days with the largest net loss. This can help you figure out when things went wrong so you can dig into what caused the worst losses and how to avoid it in the future.

Energy efficiency in regards to power consumption

In a system that consumes energy over time, you might be looking for a period where the power consumption was unusually high (in negative terms, as more consumption means less efficiency). Here, the goal would be to identify the period where energy consumption (negative performance) was at its worst, so you can optimize your system. You monitor the power usage of a machine or a household over the course of a day or week.
Some periods might have positive energy savings (efficient use), while others have negative values (wasteful energy consumption).
By applying the minimum subarray algorithm, you can find the stretch of time where energy consumption was worst, allowing you to investigate why and how to improve efficiency during that period.

The code

const impactfulFinancialLossPeriod = (days) => {

  let currentMin = days[0];   // The minimum subarray sum up to the current index
  let minSum = days[0];       // The minimum subarray sum found so far
  let start = 0;              // The starting index of the minimum subarray
  let tempStart = 0;          // Temporary start index for current potential subarray
  let end = 0;                // The ending index of the minimum subarray

  // Iterate through the array starting from the second element
  for (let index = 1; index < days.length; index++) {
    // Decide whether to start a new subarray or continue with the existing one
    if (days[index] < currentMin + days[index]) {
      currentMin = days[index];  // Start a new subarray with the current element
      tempStart = index;         // Update temporary start index to current position
    } else {
      currentMin += days[index];  // Extend the current subarray
    }

    // Update minSum if the current subarray sum is smaller
    if (currentMin < minSum) {
      minSum = currentMin;   // Update the minimum sum
      start = tempStart;     // Update the start index of the minimum subarray
      end = index;           // Update the end index to the current position
    }
  }

  return {
    period: days.slice(start, end + 1),
    startDay: start,
    endDay: end
  };
}

// Example usage with a 30 days month:
const days = [27, -50, 13, -4, 3, -2, 50, -33, -4, -2, 55, 999, 333, 12, 556, 77, -33, -11, 2, -334, 9, 55, 100, 150, 200, 250, 300, 350, -5, -100];

console.log(impactfulFinancialLossPeriod(days));  

// Output:
// period: (4) [-33, -11, 2, -334]
// startDay: 16
// endDay: 19