Small Group

Concepts Used

Heap

Difficulty Level

Hard

Problem Statement :

Given an array of N integers, we want to know whether it is possible to divide the students into contiguous groups of minimum size 3 such that in every group there are no two students of the same score and the score value of every student of the group is consecutive integers.
Print Yes if possible else print No

See original problem statement here

Examples:

Solution Approach :

Introduction :

The idea here is to refer some online programming courses to try to greedily add elements to the shortest subsequence possible before creating a new subsequence. A hash array is used to keep track of where each subsequence is currently ending, and for each subsequence ending at i, there is a minheap that keeps track of the shortest subsequence ending at i.

Description :

  • In a min-heap, the root always stores the smaller value as compared to its left & right subtree, this condition needs to be true for every node. We need to insert each item one by one such that parent is always smaller than the item itself. If parent is greater, then swap the current item with its parent.

  • If we can greedily extend a subsequence for a particular number j, we do so by adding it to the shortest subsequence ending at j-1 and then update where that subsequence ends. Otherwise, we create a new subsequence that ends at j.

  • Then, we go through all the heaps and check if any represent a subsequence with length of less than 3. If so, then it is not possible to satisfy the problem constraint, and so we immediately return false. Otherwise, we return true upon checking the lengths of all the subsequences.

extract(): Removes the minimum element from Min-Heap. Time Complexity of this Operation is O(Logn) as this operation needs to maintain the heap property (by calling heapify()) after removing root.

heapify(): Maintains the heap property for each node. If any node does not follow heap property it swaps the node with the node which is smaller ,or greater (in case of max-heap), than the node.

Below is the algorithm of above approach.

Algorithms :

Insert() :

  1. Insert the item at the last index, and increment the size by 1.
  2. Then, check if the inserted item is smaller than its parent,
  3. If yes, then swap the inserted item with its parent.
  4. If no, then do nothing.
  5. Now, go to step 2 and repeat untill we reach root (first element).

Extract() :

  1. Store the value of the first node of our heap ( temp = heap[0] ).
  2. Replace the root node with the farthest right node (last element).
  3. Decrease the size by 1. (heap[0] = heap[size-1])
  4. Perform heapify starting from the new root.
  5. Return the stored value.(temp)

Heapify () :

  1. if the heap property holds true then you are done.
  2. else if
  3. the replacement node value <= its parent nodes value
    then swap them, and repeat step 3.
  4. else
  5. swap the replacement node with the smallest child node, and
    repeat step 3.

Solutions:

#include <stdio.h>
#include <stdlib.h>


typedef struct heap_s {
    int capacity;
    int size;
    // arr[size][0] max value of sequence
    // arr[size][1] length of sequence
    int** arr;
} heap_t;

heap_t* init(int);
void insert(heap_t*, int, int);
int* top(heap_t*);
void pop(heap_t*);
int empty(heap_t*);


heap_t* init(int max)
{
    heap_t* heap = (heap_t*)malloc(sizeof(heap_t));
    heap->capacity = max;
    heap->size = 0;
    heap->arr = (int**)malloc(sizeof(int*) * (max + 1));
    return heap;
}

// if a < b
int cmp(int* a, int* b)
{
    return a[0] == b[0] ? b[1] > a[1] : b[0] > a[0];
}

void swap(int** a, int i, int j)
{
    int* tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

void insert(heap_t* heap, int val, int length)
{
    int* node = (int*)malloc(sizeof(int) * 2);
    node[0] = val, node[1] = length;
    heap->arr[++heap->size] = node;
    for (int i = heap->size; i > 1 && cmp(heap->arr[i], heap->arr[i / 2]); i /= 2) {
        swap(heap->arr, i, i / 2);
    }
}
int* top(heap_t* heap)
{
    return heap->arr[1];
}
void pop(heap_t* heap)
{
    heap->arr[1] = heap->arr[heap->size--];
    for (int i = 1; i * 2 <= heap->size;) {
        // find smaller child to compare with the current node
        int child = cmp(heap->arr[i * 2], heap->arr[i * 2 + 1]) ? i * 2 : i * 2 + 1;
        if (cmp(heap->arr[child], heap->arr[i])) {
            // swap if child is smaller
            swap(heap->arr, child, i);
            i = child;
        } else
            break;
    }
}
int empty(heap_t* heap)
{
    return heap->size == 0;
}

int isPossible(int* nums, int numsSize)
{
    heap_t* heap = init(numsSize);
    for (int i = 0; i < numsSize; i++) {
        // can't put value to the sequence any more
        while (!empty(heap) && nums[i] - top(heap)[0] > 1) {
            // find invalid sequence, return false
            if (top(heap)[1] < 3)
                return 0;
            pop(heap);
        }
        if (empty(heap) || nums[i] == top(heap)[0]) {
            // add a new sequence
            insert(heap, nums[i], 1);
        } else {
            // update the old sequence's value and length
            int length = top(heap)[1] + 1;
            pop(heap);
            insert(heap, nums[i], length);
        }
    }
    while (!empty(heap)) {
        // find invalid sequence, return false
        if (top(heap)[1] < 3)
            return 0;
        pop(heap);
    }
    return 1;
}


void swapp(int *xp, int *yp) 
{ 
    int temp = *xp; 
    *xp = *yp; 
    *yp = temp; 
} 

void selectionSort(int arr[], int n) 
{ 
    int i, j, min_idx; 
    for (i = 0; i < n-1; i++) 
    { 
        min_idx = i; 
        for (j = i+1; j < n; j++) 
          if (arr[j] < arr[min_idx]) 
            min_idx = j; 
        swapp(&arr[min_idx], &arr[i]); 
    } 
} 

int main()
{
  int t;
  scanf("%d",&t);
  while(t-->0)
  {
    int n;
    scanf("%d",&n);
    int *a = (int*)malloc(sizeof(int)*n);
    for(int i=0;i<n;i++)
     scanf("%d",&a[i]);
    selectionSort(a,n);
    if(isPossible(a, n))
     printf("Yes\n");
    else
     printf("No\n");
  }

  return 0;
}
#include <bits/stdc++.h>
using namespace std;
int parent(int i)
{
     return (i-1)/2;
}
int left(int i)
{
     return (i*2)+1;
}
int right(int i)
{
     return (i*2)+2;
}
void swap(int *a,int *b)
{
     int temp = *a;
     *a = *b;
     *b = temp;
}
void insert(int heap[],int *size, int val)
{
     heap[*size]= val;
     int i = *size;
     (*size)++;
     while(i!=0 && heap[parent(i)]>heap[i])
     {
     swap(&heap[parent(i)],&heap[i]);
     i = parent(i);
     }
}
void heapify(int heap[],int i,int size)
{
     int l = left(i);
     int r = right(i);
     int s = i;
     if(l<size && heap[l]<heap[i])
        s = l;
     if(r<size && heap[r]<heap[s])
        s = r;
     if(s!=i)
     {
     swap(&heap[i],&heap[s]);
     heapify(heap,s,size);
     }
}
int extract(int heap[],int *size)
{
     int root = heap[0];
     heap[0] = heap[*size-1];
     (*size)--;
     heapify(heap,0,*size);
     return root;
}
int main()
{
  int t;
  cin>>t;
  while(t--)
  {
  int n,k;
  cin>>n>>k;
  int *heap = (int *)malloc(sizeof(int)*n);
  int size = 0;
  for(int i=0;i<n;i++)
  {
  int t;
  cin>>t;
  insert(heap,&size,t);
  }
  int count=0,sum=0;
  while(k>=0 && size)
  {
  k -= extract(heap,&size);
  count++;
  }
  cout<<count-1<<endl;
  }
  return 0;
}
import java.util.*;
import java.io.*;
public class Main { 
     private int[] Heap; 
     private int size; 
     private int maxsize; 
     private static final int FRONT = 1; 
     public Main(int maxsize) 
     { 
          this.maxsize = maxsize; 
          this.size = 0; 
          Heap = new int[this.maxsize + 1]; 
          Heap[0] = Integer.MIN_VALUE; 
     } 
     private int parent(int pos) 
     { 
          return pos / 2; 
     } 
     private int leftChild(int pos) 
     { 
          return (2 * pos); 
     } 
     private int rightChild(int pos) 
     { 
          return (2 * pos) + 1; 
     } 
     // Function that returns true if the passed 
     // node is a leaf node 
     private boolean isLeaf(int pos) 
     { 
          if (pos >= (size / 2) && pos <= size) { 
               return true; 
          } 
          return false; 
     } 
     // Function to swap two nodes of the heap 
     private void swap(int fpos, int spos) 
     { 
          int tmp; 
          tmp = Heap[fpos]; 
          Heap[fpos] = Heap[spos]; 
          Heap[spos] = tmp; 
     } 
     // Function to heapify the node at pos 
     private void minHeapify(int pos) 
     { 
          // If the node is a non-leaf node and greater 
          // than any of its child 
          if (!isLeaf(pos)) { 
               if (Heap[pos] > Heap[leftChild(pos)] 
                    || Heap[pos] > Heap[rightChild(pos)]) { 
                    // Swap with the left child and heapify 
                    // the left child 
                    if (Heap[leftChild(pos)] < Heap[rightChild(pos)]) { 
                         swap(pos, leftChild(pos)); 
                         minHeapify(leftChild(pos)); 
                    } 
                    // Swap with the right child and heapify 
                    // the right child 
                    else { 
                         swap(pos, rightChild(pos)); 
                         minHeapify(rightChild(pos)); 
                    } 
               } 
          } 
     } 
     // Function to insert a node into the heap 
     public void insert(int element) 
     { 
          if (size >= maxsize) { 
               return; 
          } 
          Heap[++size] = element; 
          int current = size; 
          while (current != 1 && Heap[current] < Heap[parent(current)]) { 
               swap(current, parent(current)); 
               current = parent(current); 
          } 
     } 
     public int remove() 
     { 
          int popped = Heap[FRONT]; 
          Heap[FRONT] = Heap[size--]; 
          minHeapify(FRONT); 
          return popped; 
     } 
     // Driver code 
     public static void main(String[] arg) 
     { 
     Scanner sc = new Scanner(System.in);
     int t = sc.nextInt();
     while(t-->0)
     {
     int n = sc.nextInt();
     int k = sc.nextInt();
     int []a = new int[n];
     Main minHeap = new Main(n); 
     for(int i=0;i<n;i++)
     {
          a[i] = sc.nextInt();
          minHeap.insert(a[i]);
     }

          int count=0,sum=0;

     while(k>=0)
     {
          k -= minHeap.remove();
          count++;
     }

          System.out.println(count-1); 
     }
     } 
} 
Previous post Fascinating Multiple Number
Next post Beautiful Bracket String (Paid Article and Add Time Complexity)

Leave a Reply

Your email address will not be published. Required fields are marked *