{"id":1700,"date":"2020-07-01T09:38:02","date_gmt":"2020-07-01T09:38:02","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1700"},"modified":"2022-03-25T11:41:10","modified_gmt":"2022-03-25T11:41:10","slug":"small-group","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/small-group\/","title":{"rendered":"Small Group"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Heap<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given an array of N<\/code> 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.
\nPrint Yes if possible else print No<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Examples:<\/h4>\n

\"\"<\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

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<\/code>, there is a minheap that keeps track of the shortest subsequence ending at i<\/code>.<\/p>\n<\/blockquote>\n

Description :<\/h4>\n
\n
    \n
  • \n

    In a min-heap<\/strong>, the root always stores the smaller value as compared to its left<\/strong> & right<\/strong> 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. <\/p>\n<\/li>\n

  • \n

    If we can greedily extend a subsequence for a particular number j<\/code>, we do so by adding it to the shortest subsequence ending at j-1<\/code> and then update where that subsequence ends. Otherwise, we create a new subsequence that ends at j<\/code>.<\/p>\n<\/li>\n

  • \n

    Then, we go through all the heaps and check if any represent a subsequence with length of less than 3<\/code>. 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.<\/p>\n<\/li>\n<\/ul>\n

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

    heapify()<\/strong>: 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<\/strong>), than the node.<\/p>\n

    Below is the algorithm of above approach.<\/p>\n<\/blockquote>\n

    Algorithms :<\/h3>\n
    \n

    Insert()<\/strong> :<\/h4>\n
      \n
    1. Insert the item at the last index, and increment the size by 1.<\/li>\n
    2. Then, check if the inserted item is smaller than its parent,<\/li>\n
    3. If yes, then swap the inserted item with its parent.<\/li>\n
    4. If no, then do nothing.<\/li>\n
    5. Now, go to step 2<\/code> and repeat untill we reach root (first element).<\/li>\n<\/ol>\n<\/blockquote>\n

      Extract()<\/strong> :<\/h4>\n
      \n
        \n
      1. Store the value of the first node of our heap ( temp = heap[0]<\/code> ).<\/li>\n
      2. Replace the root node with the farthest right node (last element).<\/li>\n
      3. Decrease the size by 1<\/code>. (heap[0] = heap[size-1])<\/code><\/li>\n
      4. Perform heapify<\/strong> starting from the new root. <\/li>\n
      5. Return the stored value.(temp<\/strong>)<\/li>\n<\/ol>\n<\/blockquote>\n

        Heapify ()<\/strong> :<\/h4>\n
        \n
          \n
        1. if the heap property holds true then you are done.<\/li>\n
        2. else if<\/li>\n
        3. the replacement node value <= its parent nodes value
          \nthen swap them, and repeat step 3.<\/li>\n
        4. else<\/li>\n
        5. swap the replacement node with the smallest child node, and
          \nrepeat step 3.<\/li>\n<\/ol>\n<\/blockquote>\n

          Solutions:<\/h3>\n\t\t\t\t\t\t