How to find maximum number of groups needed to sort an Array?

Question

Suppose I had an array:

[1, 8, 5, 6, 10, 9, 11, 12];

I want to sort it by ascending order, but find out the maximum groups I would need to sort. In this example, the answer would be:

[1], [8,5,6], [10,9], [11], [12]: so 5

[3, 2, 1] would come out to be 1 because the entire array would need sorting.

I am at a complete loss of how to do this a nudge in the right direction would be greatly appreciated.

Bonaire

you could just iterate through the array and count the number of times n[i+1] > n[i] – Washing

Is it the maximum consecutive groups that need to be sorted ? – Peripatetic

Looks like a good case for Tarjan's Strongly Connected Components algorithm. – Broad

@Washing that doesn't work because a larger number could be in the middle of a group – Bonaire

@Dvorog it is just all groups that can be made. So even if certain numbers are sorted, such as [1] and [11], they still count as a group of 1. A group like [8,5,6] is made because within that group, you can sort all of them to their proper locations. If I added a 2 after the 9, then that entire section would be 1 group instead. – Bonaire

So if you added 2, the result would be [1,8,5,6,10,9,2],[11],[12] = 3 ? – Peripatetic

@Dvorog it would be [1], [8,5,6,10,9,2], [11], [12] = 4. The 1 is already in its correct place, so it is its own group, same as 11 and 12. – Bonaire

Answer 1

My solution uses the insertion sort algorithm, which keeps sorted elements on their places and moves unsorted elements towards the beginning of the array until they get in their place. We can use this behavior to detect groups that need to be sorted.

At each iteration, we check whether the current element is greater than or equal to the previous one. If so, we may have encountered a new group. We push the current index to a stack.

If the current element is less than previous, then we're still in the same group. We start to swap this element with previous elements until it gets in place. And at each step we check if we have crossed the boundary of the previous group. If the boundary is crossed, it means that these two groups are actually one group, so we pop the last value from the stack.

Finally, the number of groups equals to the stack size.

Here is the implementation:

public static int countGroups(int[] a) {
    if (a.length < 2) return a.length;
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    for (int i = 1; i < a.length; i++) {
        if (a[i] >= a[i - 1]) stack.push(i);
        for (int j = i; j > 0 && a[j] < a[j - 1]; j--) {
            swap(a, j, j - 1);
            if (j <= stack.peek()) stack.pop();
        }
    }
    return stack.size();
}

private static void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

And here is a JavaScript snippet with some examples:

console.log(countGroups([1, 8, 5, 6, 10, 9, 11, 12]));    //5 - [1], [8, 5, 6], [10, 9], [11], [12]
console.log(countGroups([1, 8, 5, 6, 10, 9, 2, 11, 12])); //4 - [1], [8, 5, 6, 10, 9, 2], [11], [12]
console.log(countGroups([3, 8, 5, 6, 10, 9, 2, 11, 1]));  //1 - [3, 8, 5, 6, 10, 9, 2, 11, 1]
console.log(countGroups([1, 2, 8, 6, 10, 9, 11]));        //5 - [1], [2], [8, 6], [10, 9], [11]
console.log(countGroups([1, 2, 1, 1, 10, 9, 10]));        //4 - [1], [2, 1, 1], [10, 9], [10]

function countGroups(a) {
    if (a.length < 2) return a.length;
    let stack = [0];
    for (let i = 1; i < a.length; i++) {
        if (a[i] >= a[i - 1]) stack.push(i);
        for (let j = i; j > 0 && a[j] < a[j - 1]; j--) {
            swap(a, j, j - 1);
            if (j <= stack[stack.length - 1]) stack.pop();
        }
    }
    return stack.length;
}

function swap(a, i, j) {
   let t = a[i];
   a[i] = a[j];
   a[j] = t;
}

UPDATE: If you don't need to actually sort the array, it seems that the problem can be solved in linear time:

public static int countGroupsLinear(int[] a) {
    Stack<Integer> stack = new Stack<>();
    stack.push(a[0]);
    for (int i = 1; i < a.length; i++) {
        if (a[i] >= stack.peek()) stack.push(a[i]);
        else {
            int last = stack.pop();
            while (stack.size() > 0 && a[i] < stack.peek()) stack.pop();
            stack.push(last);
        }
    }
    return stack.size();
}

Caitiff

The stack solution isn't linear time, it's quadratic in worst case if the array is reverse sorted. – Seeger

@Seeger your statement is incorrect; the stack solution is linear time since each number is pushed to the stack once and popped at most once. – Avon

You're right. I din't notice it in first go. it looked strangely like insertion sort. That's a beautiful solution too – Seeger

Answer 2

Here is the code that works out well with an array of n distinct integers. This is in C.

#include <stdio.h>
//code for the case where each element of the array is distinct 
//and greater than 0
//finding index of the maximum value in array
int maximum(int *a,int n)
{
    int i,max;
    max=0;
    for(i=0;i<n;i++)
    {
        if(a[i]>a[max])
        {
            max=i;
        }
    }
    return max;
}

//finding index of the minimum value in array(excluding zeros)
int minimum(int *a,int n)
{
    int i,min,index;
    min=100000;
    for(i=0;i<n;i++)
    {
        if(a[i]!=0 && a[i]<min)
        {
            min=a[i];
            index=i;
        }
    }
    return index;
}

//checks for the presence of a non-zero element in array
int check(int *a,int n)
{
    for(int i=0;i<n;i++)
    {
        if(a[i]!=0)
        return 1;
    }
    return 0;
}

//main function
int main()
{
    int n,j,k,max,min,slices;
    slices=0;
    scanf("%d",&n);
    int a[n];
    for(int j=0;j<n;j++)
    {
        scanf("%d",&a[j]);
    }
    //until all the elements of the array become 0
    //continue iterating to find slices
    while(check(a,n))
    {
        max=maximum(a,n);
        min=minimum(a,n);
        //if index of minimum value is greater than 
        //index of maximum value
        if(max<min)
        {
            slices=slices+1;
            for(j=0;j<n;j++)
            a[j]=0;
        }
        else
        {
            for(j=0;j<=min;j++)
            {
                a[j]=0;
            }
            slices=slices+1;
            if(check(a,n))
            {
                for(j=max;j<n;j++)
                {
                    a[j]=0;
                }
                slices=slices+1;
            }
        }
    }
    printf("slices %d",slices);
    return 0;
}

Daubery

Answer 3

This can be done by piggybacking on MergeSort Routine.

The real action takes places in the merge stage of the merge sort routine.

The idea here is for any index i of the merged array

1. If the element to be added has the same index as the index being inserted to then we know that it forms a group and we increment the group count by 1.

Suppose i/p = [1, 7, 5, 4, 2, 12]

We create a new array which stores the indices of the elements [0, 1, 2, 3, 4, 5, 6]

for the given input the first merge function will be called for left SubArray => 0 right SubArray => 1

For the 0th element of the new merged array we look at the which element we can use.

so for 0th of the new element comes from index 0, i.e. 1, which are the same so we increment the number of groups by 1. Same for index 1

2. Suppose for index i in the merged array the element from index j, where j > i has to be inserted, we for now know that the subarray from i to j could be a group if all the elements in the range [i, j] in the merged array falls with this range. In case we encounter another index to be added k which is greater that j we will update the index we are looking for to include k i.e. [i, k]. Because, if we consider only range [i, j] we will have a element at k where input[k] > input[j] thereby not forming a valid group.

Example input = [3, 2, 0, 1] which will become [0, 1, 2, 3] for the last merge the left subarray will be[1, 0] the right subarray will be[2, 3 ]`

for index 0 of the merged array we look at minimum of input[1] or input[2] which is input[2] and the index is 2, so we now know that the minimum this array comes from index 2. We continue to look until the index 3 in the merged array and updating the highest index the which contributes a group and stop when both the indices become the same

at index 1, we have choose between index 1, 3 and we find out index [3] is the next least minimum and we update the highest index to 3 and continue until index i of the merged index becomes equal to the index of the element being inserted.

It runs in O(N log N) and we get result of the indices array is the sorted indices of the input array

Seeger

Answer 4

This solution is O(N). But it works only for array with distinct numbers.

public static List<List<Integer>> countGroups(int[] arr) {

    List<List<Integer>> result = new ArrayList<List<Integer>>();

    if (arr.length < 1)
        return result;

    // create mins from right to left
    int[] mins = new int[arr.length];
    int tempMin = arr[arr.length - 1];
    for (int i = arr.length - 1; i >= 0; i--) {
        tempMin = Math.min(tempMin, arr[i]);
        mins[i] = tempMin;
    }

    // create max from left to right
    int[] maxs = new int[arr.length];
    int tempMax = arr[0];
    for (int i = 0; i < arr.length; i++) {
        tempMax = Math.max(tempMax, arr[i]);
        maxs[i] = tempMax;
    }

    // now that you have the start of intervals (mins) and end of intervals, you can
    // simply check if you are
    // still in the interval

    List<Integer> list = new ArrayList<Integer>();
    for (int i = 0; i < arr.length - 1; i++) {
        list.add(arr[i]);
        if (mins[i] != mins[i + 1] && maxs[i] != maxs[i + 1]) {
            result.add(new ArrayList<Integer>(list));
            list.clear();
        }
    }

    list.add(arr[arr.length - 1]);
    result.add(new ArrayList<Integer>(list));

    return result;
}

`

Panier

Answer 5

Here is the solution I was able to come up with, the idea is to keep an active index of the array whose value is in between current maximum and minimum values, the tricky part is keeping the current maximum that is out of context as currentCheckableMaxIndex which becomes currentMaxIndex whenever it falls in context

public static int countSubArray(int[] A) {

    int len = A.length;
    int currentActiveIndex = 0;
    int count = 0;
    for(int i = 0; i < len;){
        int currentCheckableMaxIndex = i;
        int currentMinIndex = i, currentMaxIndex = i;
        for(int j = i; j < len; j++){
            // if there is a new min value, set its index,
            // also check if there is a checkable max that we can change to the new max
            if(A[currentMinIndex] > A[j]) {
                currentMinIndex = j;

                if(A[currentMaxIndex] < A[currentCheckableMaxIndex])
                    currentMaxIndex = currentCheckableMaxIndex;
            }
            // setting only the current checkable max to avoid including a max whose index is higher than current minimum
            // will only set it to the max index if there exists a new minimum whose index is > currentCheckableMaxIndex
            if(A[currentCheckableMaxIndex] < A[j]) {
                currentCheckableMaxIndex = j;
            }
            // save the current valid index only if the value in the current index is in between the current min and max
            if(A[currentMaxIndex] >= A[j] && A[j] >= A[currentMinIndex]) currentActiveIndex = j;
        }
        // i should continue from the current valid index + 1
        i = currentActiveIndex + 1;

        count++;

        // loop will not get here again if i == len - 1, so we count the last group that would have be omitted
        if(i == len - 1) {
            count++;
            break;
        }
    }

    return count;

}

Jared

Answer 6

Same solution as proposed above, but implemented in Python 3:

def solution(A) -> int:
    if len(A) < 2:
        return len(A)

    stack = [A[0]]
    for num in A[1:]:
        if num >= stack[-1]:
            stack.append(num)
        else:
            smallest = stack.pop()
            while len(stack) > 0 and num < stack[-1]:
                stack.pop()
            stack.append(smallest)
    
    return len(stack)

Urticaceous