Recently I came across an interview question. I tried solving it but interviewer was looking for a better solution. The question is:
Given a source array containing zeroes and target array containing numbers, return the smallest number of steps in which you can obtain target from source. You are only allowed to do following operation: You can increase the values of source array elements each by 1 from index L to index R in one operation.
My thoughts:
Let array be [4,2,3,5]
cnt=0;
For each sub-array with only non-zero element, subtract minimum of that sub-array from each of the element of that sub-array. Count increases by sum of mins in each subarray
So array becomes :
After first step : [2,0,1,3] cnt+=1*2 (because only one subarray)
After second step : [0,0,0,2] cnt+=2+1 (because two subarray, each requiring an increment operation)
After second step : [0,0,0,0] cnt+=2
Can some one help in finding better algorithm? I am also thinking if segment tree / binary index tree could also be used but couldn't come up with a solution.
Instead of incrementing the zero array and transform it into given array, attack other way around - try to make given array into zero array by decrementing.
Build a segment tree on top of the given array. The segment tree should be able to answer this queries - min(left, right ) - index of minimum item between range left and right.
Start with range(0, n - 1) where n is the size of the array. At any moment, for the query(left, right) lets say the minimum element is x and the index is indx.
Now here is the trick. The idea is to NOT decrementing elements between range left to right practically because that will be difficult. Call recursively for range(left, indx - 1) and range(indx + 1, right). For left part and right part now you know, you have already decremented dx from every element. So now for any element is X, you have to handle this like X - dx.
Hope you get the idea. I am going to provide C++ implementation for this.
Please see the code and use pen & paper. You will get the idea hopefully. I've added comment on the tricky part.
class Solution {
public:
vector<int> segmentTree;
vector<int> arr;
int n;
void init() {
segmentTree.clear();
const int SIZE = pow(2, ceil(log((double) n) / log(2.0)) + 1) - 1;
segmentTree.resize(SIZE, 0);
build(1, 0, n - 1);
}
// O(n)
int build(int node, int left, int right) {
if(left == right) {
return segmentTree[node] = left;
}
int leftNode = node << 1;
int rightNode = leftNode | 1;
int mid = left + (right - left) / 2;
int leftIdx = build(leftNode, left, mid);
int rightIdx = build(rightNode, mid + 1, right);
return segmentTree[node] = (arr[leftIdx] <= arr[rightIdx]) ? leftIdx : rightIdx;
}
int query(int node, int left, int right, int x, int y) {
if(x > right or y < left) return -1;
if(left >= x and right <= y) return segmentTree[node];
int leftNode = node << 1;
int rightNode = leftNode | 1;
int mid = left + (right - left) / 2;
int leftIdx = query(leftNode, left, mid, x, y);
int rightIdx = query(rightNode, mid + 1, right, x, y);
if(leftIdx == -1) return rightIdx;
if(rightIdx == -1) return leftIdx;
return (arr[leftIdx] <= arr[rightIdx]) ? leftIdx : rightIdx;
}
int query(int x, int y) {
return query(1, 0, n - 1, x, y);
}
int convertUtil(int left, int right, int dx) {
if(left > right) return 0;
int mid = query(left, right);
int minElement = arr[mid];
int cnt = 0; // the number of operation
// dx is the amount that has been already decremented from this range
// So you have to treat every element X as (X - dx)
cnt += (minElement - dx);
cnt += convertUtil(left, mid - 1, minElement) + convertUtil(mid + 1, right, minElement);
return cnt;
}
int convert(vector<int>& arr) {
this->arr = arr;
this->n = arr.size();
init();
return convertUtil(0, n - 1, 0);
}
};
// vector<int> arr {4,2,3,5};
// cout << Solution().convert(arr); // OUTPUT: 7