Minimum Difference

Concepts Used

Heap

Difficulty Level:

Hard

Problem Statement :

Given N sectors and two integers P and Q, our task is to find Q closest sectors to P sector.

See original problem statement here

Solution Approach :

Introduction :

Idea is to create a max-heap of Q sectors, in order to get Q closest sectors to P, we need to make the heap of the absolute differences with P of all the sectors and find Q closest sectors from these differences.

Method 1 :

By referring some online programming courses, Sort the array containing sectors in decreasing order using any sorting algorithm. Now take the absolute difference of these elements from P and store the differences. Iterate through i=Q to N, and store the Q minimum values in the array, now print Q original values from which we had taken differences.

Method 2 :

  • Geneate a max-heap from the sectors of size Q.
    In a max-heap, the root always stores the larger 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 larger than the item itself. If parent is smaller, then swap the current item with its parent.
  • After generating max-heap of first Q sectors, iterate through i=Q to N and check if any ith value is smaller than the top value of our heap `sector[i]* Now print the values in the heap.
    extract(): Removes the maximum element from Max-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.

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 largest child node, and
    repeat step 3.

Example:

Solutions:

#include <stdio.h>

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 lar = i;
  if(l<size && heap[l]>heap[i])
   lar = l;
  if(r<size && heap[r]>heap[lar])
   lar = r;
  if(lar!=i)
  {
    swap(&heap[i],&heap[lar]);
    heapify(heap,lar,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;
  scanf("%d",&t);
  while(t--)
  {
    int n,p,q;
    scanf("%d %d %d",&n,&p,&q);
    int *heap = (int *)malloc(sizeof(int)*q);
    int size = 0;
    for(int i=0; i<q; i++)
    {
      int t;
      scanf("%d",&t);
      insert(heap,&size,t);
    }
    for(int i=q;i<n;i++)
    {
      int t;
      scanf("%d",&t);
      if(t<heap[0])
      {
        extract(heap,&size);
        insert(heap,&size,t);
      }
    }

      while(q--)
      {
        printf("%d ",extract(heap,&size));
      }
      printf("\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 lar = i;
if(l<size && heap[l]>heap[i])
lar = l;
if(r<size && heap[r]>heap[lar])
lar = r;
if(lar!=i)
{
    swap(&heap[i],&heap[lar]);
    heapify(heap,lar,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,p,q;
    cin>>n>>p>>q;
    pair<int,int> *heap[];
    int size = 0;
    for(int i=0; i<q; i++)
    {
    int t;
    cin>>t;
    insert(heap,&size,t);
    }
    for(int i=q;i<n;i++)
    {
    int t;
    cin>>t;
    if(t<heap[0])
    {
        extract(heap,&size);
        insert(heap,&size,t);
    }
    }
    while(q--)
    {
        cout<<extract(heap,&size)<<" ";
    }
    cout<<endl;

}
return 0;
}
import java.util.Scanner;
public class Main {
public static class MaxHeap { 
    private class Pair {
        public int first;
        public int second;
        Pair(int a, int b) {
            this.first = a;
            this.second = b;
        }
    }
    private Pair[] Heap;
    private int size; 
    private int maxsize; 

    public MaxHeap(int maxsize) 
    { 
        this.maxsize = maxsize; 
        this.size = 0; 
        Heap = new Pair[this.maxsize + 1]; 
        Heap[0] = new Pair(0, Integer.MAX_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; 
    } 

    private boolean isLeaf(int pos) 
    { 
        if (pos >= (size / 2) && pos <= size) { 
            return true; 
        } 
        return false; 
    } 

    private void swap(int fpos, int spos) 
    { 
        Pair tmp; 
        tmp = Heap[fpos]; 
        Heap[fpos] = Heap[spos]; 
        Heap[spos] = tmp; 
    } 

    private void MaxHeapify(int pos) 
    { 
        if (pos > size) 
            return; 
        int left = leftChild(pos);
        int right = rightChild(pos);
        if (left > size && right > size) 
            return;

        if (right > size) {
        if( Heap[pos].second < Heap[left].second) {
            swap(pos, left);
            MaxHeapify(left);
        } 
            return;
        }
        if (Heap[pos].second < Heap[leftChild(pos)].second ||  
            Heap[pos].second < Heap[rightChild(pos)].second) 
            { 

            if (Heap[leftChild(pos)].second > Heap[rightChild(pos)].second) 
            { 
                swap(pos, leftChild(pos)); 
                MaxHeapify(leftChild(pos)); 
            } 
            else 
            { 
                swap(pos, rightChild(pos)); 
                MaxHeapify(rightChild(pos)); 
            } 
        } 
    } 

    public void insert(int a, int b) 
    { 
        Heap[++size] = new Pair(a, b); 

        int current = size; 
        while (Heap[current].second > Heap[parent(current)].second) { 
            swap(current, parent(current)); 
            current = parent(current); 
        } 
        MaxHeapify(current);
    } 


    public int extractMax() 
    { 
        Pair popped = Heap[1]; 
        Heap[1] = Heap[size--]; 
        MaxHeapify(1); 
        return popped.first; 
    } 
    public int top() {
        return Heap[1].second;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public void print() 
    { 
        for (int i = 1; i <= size; i++) { 
            System.out.print("(" + Heap[i].first + "," + Heap[i].second + ")" + " ");
        } 
        System.out.println();
    } 
}

    public static void main(String[] arg) 
    { 
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
        while(t > 0) {
            t--;
            int n = s.nextInt();
            int p = s.nextInt();
            int q = s.nextInt();
            MaxHeap heap = new MaxHeap(n);
            for (int i=0; i<q; i++) {
                int a = s.nextInt();
                heap.insert( a,Math.abs(p - a));
            }
            for (int i=q; i<n; i++) {
                int a = s.nextInt();
                int diff = Math.abs(p - a);
                if (diff< heap.top()) {
                    heap.extractMax();
                    heap.insert(a, diff);
                }
            }
            while(!heap.isEmpty()) {
                System.out.print(heap.extractMax() + " ");
            }
            System.out.println();
        }
    } 
}
Previous post Kth Largest element
Next post Heap Sort

Leave a Reply

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