Count maximum stable segments

Question

Problem Statement:

A warehouse manages a line of containers prepared for shipment. Each container has a specified mass, provided in the list massList, where massList[i] represents the mass of the 𝑖th container in the lineup.

Containers are grouped into segments, where each segment consists of one or more consecutive containers. For example, given masses [3, 6, 3], valid segments include [3], [6], [3, 6], [6, 3], and [3, 6, 3]—but not [3, 3], since the containers are not adjacent.

A segment is considered stable if the final container does not have the maximum mass among all containers in that segment. For instance:

[3, 9, 4, 7] is stable (last mass is 7, but the maximum is 9).

[4, 7, 2, 7] is not stable (last mass is 7, which equals the max).

Divide the sequence into the maximum number of stable segments such that:

Every container is part of exactly one segment.

Each segment uses a contiguous part of the list.

Every segment must be stable.

If it's impossible to create a stable segment, return 0.

Example:

massList = [1, 2, 3, 2, 6, 3] One valid partitioning: [1, 2, 3, 2] and [6, 3]

Both are stable segments.

No other partition yields more than 2 stable segments.

Answer: 2

Constraints:

2≤n≤10^5
1≤massList[i]≤10^9

I have used greedy approach to solve this:

We make one pass through the list and maintain:

max: the maximum mass seen so far in the current segment.

stableCount: how many stable segments we’ve found.

import java.util.*;

class ContainerPlanner {
    public static int getMaxStableSegments(List<Integer> massList) {
        int n = massList.size();    
        int max = 0;
        int stableCount = 0;

        for (int i = 0; i < n; i++) {
            int m = massList.get(i);
            max = Math.max(m, max);
            if (m < max && max > 0) {
                stableCount++;
                max = 0;
            }
        }

        return stableCount;
    }

    public static void main(String[] args) {
        System.out.println(getMaxStableSegments(Arrays.asList(1, 2, 3, 2, 6, 3))); // Output: 2
        System.out.println(getMaxStableSegments(Arrays.asList(8, 5, 4, 7, 2)));    // Output: 2
        System.out.println(getMaxStableSegments(Arrays.asList(4, 3, 6, 5, 3, 4, 7, 1))); // Output: 3
        System.out.println(getMaxStableSegments(Arrays.asList(
            10, 5, 6, 4, 7, 6, 4, 2, 7, 1, 4, 6, 3, 4, 5, 1, 7, 5, 4, 6, 7, 8, 4, 6, 1, 9, 9
        ))); // Output: 1
    }
}

I have added some test cases in main method, out of 4 test cases 1 test case fails

Expected output is 1 but my solution is returning 10 for test case

getMaxStableSegments(Arrays.asList(
            10, 5, 6, 4, 7, 6, 4, 2, 7, 1, 4, 6, 3, 4, 5, 1, 7, 5, 4, 6, 7, 8, 4, 6, 1, 9, 9
        )); // Output: 1

My current greedy approach is incorrect because it fails to handle edge cases where it's impossible to divide all masses into valid stable segments. As a result, it's returning values like 10 instead of the correct answer, such as 1.

What would be the correct and efficient approach to solve this problem, ensuring all masses are included in valid stable segments while maintaining optimal time complexity, that is less than O(n^2)?

Answer 1

Since each segment requires an element that is higher than its last element, each segment must include a "downward step" from a higher element to a smaller element that immediately follows it.

Start by finding the shortest possible end segment, by searching from the end for any element that is higher than the last one.

Then find the maximum number of disjoint downward steps before this last segment. Add 1 for the last segment, and this is the answer.

Proof

Since every segment requires a downward step, and we've consumed as few elements as possible for the end segment, there cannot possibly be more additional segments than there can be disjoint downward steps in the remaining elements.

Furthermore, given some disjoint downward steps before the last segment, we can easily make a segment out of each and every one of them, because any left over elements in the array can be added to the following segment.

Maximum Disjoint Downward Steps

To count the maximum number of disjoint downward steps, just find every strictly decreasing subarray. If it has length m, then it can be divided into floor(m/2) downward steps. [4,3,2,1], for example, can be divided into 2 steps, [4,3] and [2,1], but given just [3,2,1], you can only choose one downward step. You'll get the same count if you just greedily consume downward steps as you find them.

Adding up all these counts is easy to do in linear time, and that's how long the whole algorithm takes.

Here is your Java implementation fixed:

import java.util.*;

public class ContainerPlanner {
    public static int getMaxStableSegments(List<Integer> massList) {
        int len = massList.size();
        if (len < 2) {
            return 0;
        }
        int endSegStart = len-1;
        int lastVal = massList.get(endSegStart);
        while(endSegStart >= 0 && massList.get(endSegStart) <= lastVal) {
            --endSegStart;
        }
        if (endSegStart < 0) {
            return 0;
        }
        int count = 0;
        for (int pos=0; pos<endSegStart-1; ++pos) {
            if (massList.get(pos) > massList.get(pos+1)) {
                ++pos; // consume adjacent element
                ++count;
            }
        }
        return count+1;
    }

    public static void main(String[] args) {
        System.out.println(getMaxStableSegments(Arrays.asList(1, 2, 3, 2, 6, 3))); // Output: 2
        System.out.println(getMaxStableSegments(Arrays.asList(8, 5, 4, 7, 2)));    // Output: 2
        System.out.println(getMaxStableSegments(Arrays.asList(4, 3, 6, 5, 3, 4, 7, 1))); // Output: 3
        System.out.println(getMaxStableSegments(Arrays.asList(
            10, 5, 6, 4, 7, 6, 4, 2, 7, 1, 4, 6, 3, 4, 5, 1, 7, 5, 4, 6, 7, 8, 4, 6, 1, 9, 9
        ))); // Output: 1
    }
}```

Answer 2

Try it from the last one to the first one, like this:

import java.util.Arrays;
import java.util.List;

public class ContainerPlanner {
    public static int getMaxStableSegments(List<Integer> massList) {

        int stableCount = 0;
        int ref = 0;
        int lastStableIndex = massList.size() - 1;

        while (lastStableIndex > 0) {
            for (int i = lastStableIndex; i >=0 ; i--) {
                if(ref == 0) {
                    ref = massList.get(i);
                    lastStableIndex = i;
                } else if(massList.get(i) > ref) {
                    stableCount++;
                    ref = 0;
                    lastStableIndex = i-1;
                }
            }
            if(stableCount == 0) {
                break;
            }
            lastStableIndex--;
            ref = 0;
        }

        return stableCount;
    }

    public static void main(String[] args) {
        System.out.println(getMaxStableSegments(Arrays.asList(1, 2, 3, 2, 6, 3))); // Output: 2
        System.out.println(getMaxStableSegments(Arrays.asList(8, 5, 4, 7, 2)));    // Output: 2
        System.out.println(getMaxStableSegments(Arrays.asList(4, 3, 6, 5, 3, 4, 7, 1))); // Output: 3
        System.out.println(getMaxStableSegments(Arrays.asList(1, 2, 3, 4, 5, 6, 7))); // Output: 0
        System.out.println(getMaxStableSegments(Arrays.asList(
                10, 5, 6, 4, 7, 6, 4, 2, 7, 1, 4, 6, 3, 4, 5, 1, 7, 5, 4, 6, 7, 8, 4, 6, 1, 9, 9
        ))); // Output: 1
    }
}

Later edit:

after @maraca comment, I came back at the code and not only fixed the issue, but simplified it a lot.

public static int getMaxStableSegments2(int... a) {
    if (a.length < 2) return 0;

    int i = a.length - 2;

    while (i >= 0 && a[i] <= a[a.length - 1]) i--;
    if (i < 0) return 0;
    int count = 1;

    while (i >= 2) {
        if(a[i-1] < a[i-2] ) {
            count++;
            i -= 2;
        } else {
            i--;
        }
    }
    return count;
}

Tested it with different other cases and works fine.

public static void main(String[] args) {
    System.out.println(getMaxStableSegments2() + " = 0");// Output: 2
    System.out.println(getMaxStableSegments2(1) + " = 0");// Output: 2
    System.out.println(getMaxStableSegments2(10, 9, 8, 9, 8, 9, 8, 7) + " = 3");// Output: 2
    System.out.println(getMaxStableSegments2(10, 9, 8, 7, 9, 8, 7, 9, 8, 7) + " = 4");// Output: 2
    System.out.println(getMaxStableSegments2(1, 2, 3, 4) + " = 0");
    System.out.println(getMaxStableSegments2(3,2,2,1) + " = 2");
    System.out.println(getMaxStableSegments2(2,2,2,2) + " = 0");
    System.out.println(getMaxStableSegments2(10, 5, 5, 5, 6, 4, 3) + " = 2");// Output: 2
    System.out.println(getMaxStableSegments2(1, 2, 3, 2, 6, 3) + " = 2");
    System.out.println(getMaxStableSegments2(8, 5, 4, 7, 2) + " = 2");    // Output: 2
    System.out.println(getMaxStableSegments2(4, 3, 6, 5, 3, 4, 7, 1) + " = 3"); // Output: 3
    System.out.println(getMaxStableSegments2(1, 2, 3, 4, 5, 6, 7) + " = 0"); // Output: 0
    System.out.println(getMaxStableSegments2(
            10, 5, 6, 4, 7, 6, 4, 2, 7, 1, 4, 6, 3, 4, 5, 1, 7, 5, 4, 6, 7, 8, 4, 6, 1, 9, 9
    ) + " = 1"); // Output: 1
}

My strategy was to get the most optimistic scenario, where all segments were made of 2 weights. Loop it in reverse, and if one group is not stable, add the right one to the last group and decrease the index by one.