Swap Sum

Last Updated on March 25, 2022 by Ria Pathak

Concepts Used

Heap

Difficulty Level

Medium

Problem Statement :

We are given N elements with an integer S. We want to find such a sub-array that has the maximum possible sum after applying at-most S swaps. The task is to print the sum of that sub-array.

See original problem statement here

Solution Approach :

Introduction :

Idea is to create two heaps, one min-heap H1 & one max-heap H2. We will use min-heap to store the items that are in the subarray which is currently into the consideration and max-heap to store the items that are not the part of the considered sub-array. Now replace every element in H1 which is smaller than the largest element in H2 also untill there are swaps left.

Method 1:

Idea is to iterate for every element and divide every subarray
into two parts :

• subarray which is currently being considered.
• subarray which is not the part of the considered subarray.

We will sort the first sub array in increasing order and the second one is decreasing order. Now while there are swaps left and the smallest element of the first subarray is smaller than the greatest element of the second subarray, we will keep swapping these two values (smallest and greatest).

Method 2:

• We need to geneate a min-heap H1 and max-heap H2.
• 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.
• 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.
• While creating max-heap and min-heap for each subset, lets say for a subset s, we will swap the values top value of H1 with the top value H2, untill there are swaps left and the top value of H2 is greater than H1 and keep updating the maximum answer after each iteration. F

extract(): Removes the minimum/maximum element from Min-Heap or 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.

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/larger 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 <= (or =>) its parent nodes value
   then swap them, and repeat step 3.
4. else
5. swap the replacement node with the smallest/largest child node, and
   repeat step 3.

Example

Solutions:

#include <bits/stdc++.h>
 using namespace std;

  class heap {
    public:
          int *Heap;
          int N;
          int maxsize;
          bool reverse;

          heap(int maxsize) {
             this->maxsize = maxsize;
             this->Heap = (int *)malloc(sizeof(int)*maxsize+1);
             this->N = 0;
         }

          heap(int maxsize, bool reverse) {
             this->maxsize= maxsize;
             this->Heap = (int *)malloc(sizeof(int)*maxsize+1);
             this->reverse = reverse;
         }


          bool comp(int a, int b) {
             if (reverse) {
                 return Heap[a] > Heap[b];
             } else {
                 return Heap[a] < Heap[b];
             }
         }

         void insert(int val) {
             Heap[++N] = val;
             heapify_up(N);
         }

          int size() {
             return N;
         }

          void heapify_up(int n) {
             while (n > 1 && comp(n, n/2)) {
                 swap(n, n/2);
                 n = n/2;
             }
         }
         void heapify_down(int n) {
             while (2 * n <= N) {
                 int j = 2 * n;
                 if (j < N && !comp(j, j+1)) j++;
                 if (comp(n, j)) break;
                 swap(n, j);
                 n = j;
             }
         }



         bool isEmpty() {
             return N == 0;
         }

         int top() {
             return Heap[1];
         }

         void pop() {
             Heap[1] = Heap[N--];
             heapify_down(1);
         }

         void swap(int a, int b) {
             int temp = Heap[a];
             Heap[a] = Heap[b];
             Heap[b] = temp;
         }

     };
 int main()
 {
         int n ;
         int s;
         cin>>n>>s;
         int a[n];
         for (int i = 0; i < n; i++) {
             cin>>a[i] ;
         }
         int ans = INT_MIN;
         for (int i = 0; i < n; i++) {
             for (int j = i; j < n; j++) {
                 int curans = 0;
                 heap *minheap = new heap(n);
                 heap *maxheap = new heap(n, true);

                 for (int k = 0; k < n; k++) {
                     if (k >= i && k <= j) {
                         curans += a[k];
                         minheap->insert(a[k]);
                     } else {
                         maxheap->insert(a[k]);
                     }
                 }

                 ans = max(ans, curans);

                 for (int k = 1; k <= s; k++) {
                     if (maxheap->isEmpty() || minheap->isEmpty() || minheap->top() >= maxheap->top()) {
                         break;
                     }

                     curans -= minheap->top();
                     minheap->pop();
                     curans += maxheap->top();
                     maxheap->pop();

                     ans = max(ans, curans);
                 }
             }
         }

         cout<<ans<<endl;
 } 

import java.util.Scanner;

public class Main {
    public static class Heap {
        private int[] Heap;
        private int N;
        private int maxsize;
        private boolean reverse;

        public Heap(int maxsize) {
            this.maxsize = maxsize;
            this.Heap = new int[maxsize + 1];
            this.N = 0;
        }

        public Heap(int maxsize, boolean reverse) {
            this(maxsize);
            this.reverse = reverse;
        }


        private boolean comp(int a, int b) {
            if (reverse) {
                return Heap[a] > Heap[b];
            } else {
                return Heap[a] < Heap[b];
            }
        }

        public void insert(int val) {
            Heap[++N] = val;
            heapify_up(N);
        }

        public int size() {
            return N;
        }

        private void heapify_up(int n) {
            while (n > 1 && comp(n, n/2)) {
                swap(n, n/2);
                n = n/2;
            }
        }
        private void heapify_down(int n) {
            while (2 * n <= N) {
                int j = 2 * n;
                if (j < N && !comp(j, j+1)) j++;
                if (comp(n, j)) break;
                swap(n, j);
                n = j;
            }
        }



        public boolean isEmpty() {
            return N == 0;
        }

        public int top() {
            return Heap[1];
        }

        public void pop() {
            Heap[1] = Heap[N--];
            heapify_down(1);
        }

        private void swap(int a, int b) {
            int temp = Heap[a];
            Heap[a] = Heap[b];
            Heap[b] = temp;
        }

    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int s = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int curans = 0;
                Heap minheap = new Heap(n);
                Heap maxheap = new Heap(n, true);

                for (int k = 0; k < n; k++) {
                    if (k >= i && k <= j) {
                        curans += a[k];
                        minheap.insert(a[k]);
                    } else {
                        maxheap.insert(a[k]);
                    }
                }

                ans = Math.max(ans, curans);

                for (int k = 1; k <= s; k++) {
                    if (maxheap.isEmpty() || minheap.isEmpty() || minheap.top() >= maxheap.top()) {
                        break;
                    }

                    curans -= minheap.top();
                    minheap.pop();
                    curans += maxheap.top();
                    maxheap.pop();

                    ans = Math.max(ans, curans);
                }
            }
        }

        System.out.println(ans);
    }

}

[forminator_quiz id="1739"]

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.