Lightsabers Problem | Hashing | Programming in C++
In this blog we’ll solve Lightsabers problem that is a well known and standard problem based on hashing concept that uses two pointers technique.
Problem Description:
We are given two arrays of integers A and B of size N and M respectively.
The goal is to select some continuous interval in A such that there are exactly B[0] elements with value 1, B[1] elements with value 2 and so on ending with B[m-1] elements with value m.
However, it is not always possible to select such an interval from the given array therefore it is allowed to remove some elements from A in order to achieve the goal.
Find and return the minimum number of elements to be removed from A in order to achieve the goal. If it is not possible to achieve the goal return -1 instead.
Constraints
1 <= N, M <= 100000
1 <= A[i] <= M
0 <= B[i] <= NFor Example
Input 1:
A = [1, 2, 3, 4, 1]
B = [2, 1, 1, 0]
Output 1:
1 (Remove element 4 and consider all the remaining elements).Input 2:
A = [1, 1, 2, 2, 2]
B = [1, 2, 1]
Output 2:
-1 (The count of 3 required is 1 i.e. B[2]=1, but 3 is not present in A, so requirement doesn't satisfy)Input 3:
A = [3, 3, 3, 3, 3, 4, 2, 1, 1, 3, 1, 2, 1, 1, 1, 4, 4, 1, 1, 1, 2, 1, 2, 3, 3, 3, 2, 2, 2, 4]
B = [2, 0, 4, 0]
Output 2:
2 (From position 2 to 9, we can remove elements 4 & 2 from array A to achieve the goal)
Solution Discussion:
This problem can be solved using two maps(Hashmap in Java) and two pointers.
Since the indices+1(position) in array B represents the integer elements and the values represents count. i.e. for B = [2, 1, 1, 0], means required count of 1 is 2, count of 2 is 1, count of 3 is 1 and count of 4 is 0. We’ll use a map “required” to store the position as key and count as value.
In solution approach is very much similar to sliding window with not-fixed window size using two pointers. We’ll use the 2nd map “mb” to store the required element’s count in my current working window. And two pointers, “ini” will be used to store the initial location(beginning) of solution window and “minn” for minimum number of elements to be removed from A respectively. For currently working window, we’ll temporarily store these two pointer values in “tini” & “tminn”.
We’ll also use a count flag “threshold” that will store the count of the required elements added in the current map mb to check if we achieve our goal or not irrespective of the minimum size constraint.
- We’ll iterate through every element in array A to check if the current element is required or not according to map “required”
- If the current element is required, we’ll increment the count in the map mb which was initialized with all zero count for only required numbers and increase the size of current window.
- If the count becomes more than required then we’ll check if we can reduce the size of the current window by proceeding our tini pointer ahead. We’ll update our tini & tminn pointers accordingly.
- If the count is not more than required the we’ll increment count to flag threshold.
- If the current element is not required then we’ll add nothing in the map mb, but will increase the size of the current window
- If the flag threshold count is equal to required count of elements in array B, we’ll update the solution pointers ini and minn by comparing with tini & tminn.
- At the end we’ll check if the threshold satisfies the required count, if true we’ll return minimum number of elements to be removed from A i.e. return minn. Otherwise return -1.
PS: Don’t forget to add a clap if you understood the approach and intuition behind this solution.
Code:
int lightsabers(vector<int> &A, vector<int> &B) {
map<int, int> required, mb;
int ini=-1, tini = -1, minn = INT_MAX, tminn = INT_MAX;
long long threshold = 0, thresholdPass = 0;
int n = A.size(), m = B.size();
for(int i=0;i<m;i++) {
mb[i+1] = 0;
required[i+1] = B[i];
thresholdPass+=B[i];
}
for(int i=0;i<n;i++) {
int c = A[i];
if(mb.find(c)!=mb.end()) {
if(mb[c]>=required[c]) {
if(A[tini] == c) {
tminn++;
mb[c]++;
int p = tini;
for(p=tini;p<i;p++) {
int x = A[p];
if(mb.find(x)!=mb.end()) {
if(mb[x]>required[x]){
mb[x]--;
tminn--;
continue;
}
else {
break;
}
}
}
tini = p;
}
else {
tminn++;
mb[c]++;
}
}
else {
if(threshold==0) {
tini = i;
tminn = 0;
}
threshold++;
mb[c]++;
}
}
else {
if(threshold==0) continue;
tminn++;
}
if(threshold == thresholdPass) {
if(minn>tminn) {
minn = tminn;
ini = tini;
}
}
}
int ans = -1;
if(threshold == thresholdPass)
ans = minn;
return ans;
}For comments over every line of code please refer this link: bit.ly/lightsaberscpp
Time & Space Complexity:
In the above approach, during the traversal we are accessing the array A’s each element max 2 times. If the size of the array A is n and B is m respectively, then the time complexity of this solution would be O(n+m).
Space complexity of this solution is 2 * m since we are using two maps each of size same as B.
Further Optimization:
There’re always room for improvement. One hint for improving the space complexity is to use array B itself instead of using map “required”.
Please add a clap 👏🏻 over this blog if you liked it.
Would love to receive your feedback/corrections/suggestions/requests in the comments section. ✌💖
Happy Coding < 3
