Approach
To solve this problem, we will use the Min Heap data structure. We will go through each element of the array and push it in the Min Heap. We will also add the element to the sum variable, which will keep track of the prefix sum of the current element.
If the prefix sum becomes negative, we subtract the most negative element from the heap and pop that element from the heap.
As it is a Min Heap, the most negative element will be present at the top of the heap. We are using Min Heap in this solution as it is very easy and quick to access the minimum element from any current step.
Steps of Algorithm
-
Take input of vectors from the user.
- Create an empty Min Heap using Priority Queue.
- Initialize the sum variable as 0.
- Run a for loop from 0 to n(size of vector)
- Add the value of the current element of the vector to the sum
- Add the current element of the vector to the Min Heap
-
Check if the sum has become negative
-
If the sum is negative
- Subtract the most negative/top element from the sum
- Pop the top element from the Min Heap
-
Else
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> vec, int n)
{
priority_queue<int, vector<int>, greater<int>> min_heap; //Creating the Min Heap
int sum = 0; //Initializing sum as 0
for (int i = 0; i < n; i++)
{
sum += vec[i]; //Adding current element's value to sum
min_heap.push(vec[i]); //Pushing current element to heap
if (sum < 0) //If sum becomes negative
{
int a = min_heap.top();
sum -= a; //Subtract top element's value from sum
min_heap.pop(); //Pop the top element from heap
}
}
return min_heap.size(); //return the ans
}
int main()
{
vector<int> vec;
int n, x;
cout << "Enter the size of the array:" << endl;
cin >> n;
cout << "Enter the elements:" << endl;
for (int i = 0; i < n; i++)
{
cin >> x;
vec.push_back(x);
}
cout << "Length of the longest subsequence is: " << solve(vec, n);
return 0;
}
You can also try this code with Online C++ Compiler
Input:
Enter the size of the array:
6
Enter the elements:
-1 6 7 -15 -3 -1
You can also try this code with Online C++ Compiler
Output:
Length of the longest subsequence is: 4
You can also try this code with Online C++ Compiler
Complexity Analysis
Time Complexity
O(n*logn) as we are traversing through a for loop ‘n’ number of times. The push and pop operations of priority queue take O(logn) time, making the overall time complexity O(n*logn). Here, n refers to the number of elements in the input vector.
Space Complexity
O(n), as we are using a priority queue of size n. Here, n refers to the number of elements in the input vector.
Dry Run of test cases
Let’s look at the dry run of Test Case 1 to understand the problem better.
The input array is,
-1, 6, 7, -15, -3, -1
Initially, sum = 0, and the Min Heap is also empty.
-1 is inserted to the Min Heap, and sum = -1.
But, as the sum becomes negative, we pop the top element from the Heap.
The next element, i.e., 6 is inserted in a heap, and the new sum becomes 6.
We then go to the next element of the vector, i.e., 7. The current sum becomes 13 (6+7). Hence, 7 is also inserted into the heap.
The next element is -15, and adding it makes the sum negative.
The sum becomes -2, so we again pop the top element of the heap, i.e., -15.
We also deduct -15 from our sum, making sum = 13.
The next element in the vector is -3; adding it to our sum makes it 10, which is a positive number. So, it is also added to the Heap.
We finally reach the last element of the vector, i.e., -1, and we add it to the current sum. It is also pushed into the Heap.
So our current sum is 9, and our Min Heap will look like this,
In the end, the size of our Min Heap is 4, indicating the length of the longest subsequence.
Frequently Asked Questions
What is Min Heap data structure?
Min Heap is a binary tree, where the root node of the tree has a value less than its children. Like the root node, the other internal nodes also need to have a smaller value than their respective children.
What is meant by the subsequence of an array?
Subsequence refers to a non-contiguous sequence of a given array, obtained by deleting one or more elements from the original array.
Is the longest subsequence the same as the longest subarray for a given array?
No, they are not the same. Longest subsequent refers to the longest possible non-contiguous sequence for a given array, but subarray refers to the longest possible contiguous section.
In which type of problems should we use Heap?
In problems where you have to find the minimum element (Min Heap) and maximum(Max Heap) element from a list of elements very quickly, Heap should be used.
Conclusion
In this blog, we saw how to solve the given problem using the Min Heap data structure.
We hope you completely understand the solution, but if you are new to Min Heap, we suggest you go through this blog to understand the critical concepts related to it.
Recommended Readings:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Happy learning, Ninja!
84+ registered