Directi Interview Question
SDE1sCountry: India
Interview Type: Phone Interview
Taking same example but with 2 value of s[] , e[] and h[].
a[] = [2,4,8,6,7]
s[] = [1,0]
e[] = [3,4]
h[] = [5,4]
o/p = [4,4,4,4,4] max = 4
for(int i=0;i<s.length;i++) {
int start = s[i];
int end = e[i];
while(start < end) {
if(a[start] > h[i]) {
a[start] = h[i];
}
start++;
}
}
findMax() // iterate array to find maximum in O(n)
Time complexity in worst case will be- O(k*n)
k is the length of s[] . and n is length of a[]
It Can also be solve by using time overlap with stack algorithm.
I have think of a O(n+m) solution, it would satisfied the questions but it seems odd, like a hack to the question.
- Dito9 February 01, 20171) O(M) find the minimum number in array H[] -> "v_min"
2) O(N) iterate over array a[] replacing higher values than "v_min" with "v_min" the max value will be "v_min"