Last Updated on March 25, 2022 by Ria Pathak
Concepts Used
Heap
Difficulty Level
Hard
Problem Statement :
Given an array of
Nintegers, 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 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 ati.
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 atj-1and then update where that subsequence ends. Otherwise, we create a new subsequence that ends atj.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() :
- Insert the item at the last index, and increment the size by 1.
- Then, check if the inserted item is smaller than its parent,
- If yes, then swap the inserted item with its parent.
- If no, then do nothing.
- Now, go to step
2and repeat untill we reach root (first element).
Extract() :
- Store the value of the first node of our heap (
temp = heap[0]).- Replace the root node with the farthest right node (last element).
- Decrease the size by
1.(heap[0] = heap[size-1])- Perform heapify starting from the new root.
- Return the stored value.(temp)
Heapify () :
- if the heap property holds true then you are done.
- else if
- the replacement node value <= its parent nodes value
then swap them, and repeat step 3.- else
- 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);
}
}
}
[forminator_quiz id="1702"]
This article tried to discuss Heap. Hope this blog helps you understand and solve the problem. To practice more problems on Heap you can check out MYCODE | Competitive Programming.