Approach
Brute Force Approach
Let us talk about the brute force approach. In the brute force approach we check for every (i,j) pair and find the pair having maximum value B[i]+B[j] + abs(A[i]-A[j]).
As we check for every (i,j) pair, the time complexity will be O(NxN).
The extra space complexity will be O(1) as we would only have one variable to store the answer. However, the input array contains N elements, so the space complexity is O(N).
Efficient Approach
Now, let us see an efficient approach.
We can see that B[i]+B[j] + abs(A[i]-A[j]) and abs(A[i]-A[j])<=k can be one of the two cases
- B[i]+B[j] + A[i]-A[j] = (B[i] + A[i]) + (B[j]-A[j]) and 0<=A[i]-A[j]<=k
- B[i]+B[j]- A[i]+A[j] = (B[i] - A[i]) + (B[j]+A[j]) and 0<=A[j]-A[i]<=k
Let us consider the second case where we have to find (i,j) such that (B[i] - A[i]) + (B[j]+A[j]) is maximum and 0<=A[j]-A[i]<=k
So our idea is to iterate through A and find a j such that 0<=A[j]-A[i]<=k and (B[i] - A[i]) + (B[j]+A[j]) is maximum for that iteration.
So now the problem is that for index i, there may be multiple number of j’s such that 0<=A[j]-A[i]<=k. So finding the j such that (B[i] - A[i]) + (B[j]+A[j]) is maximum will not be efficient if we check for each j.
Now for same i, the value of (B[i] - A[i]) + (B[j]+A[j]) only depends on the (B[j]+A[j]).
As 0<=A[j]-A[i]<=k, we can see that sorting the arrays based on A will help us because as A[i] increases, A[j] also increases.
Now we sort both the arrays based on A. Now, as i increases, the A[i] increases, so the j increases. Thus we get all the required elements in front of it.
Consider :
A=[1,100,10,91,20,11]
B=[4,5,19,18,18,2]
K=10
Now for i=0(0 based indexing), A[i]=A[0]=1 and so j=2 and j=5 satisfies abs(A[i]-A[j])<=k.
For i=1, j=3 satisfies.
For i=2, A[i]=10 and so j=0, j=4 and j=5 satisfies.
But now, we sort the array based on of A.
A= [1, 10, 11, 20, 91, 100]
B= [4, 19, 2, 18, 18, 5]
Now for i=0, j=1,2 satisfies the condition 0<=A[j]-A[i]<=k
For i=1, j= 2 and 3 satisfies the condition 0<=A[j]-A[i]<=k
So we can see that by sorting on A, the indices j which satisfies the condition 0<=A[j]-A[i]<=k are continuous and they are greater than the current index. Thus the indices satisfying the condition are (i+1,i+2,... j).
Now, finding the maximum value among those indices can be easily done using a Segment Tree. We can build the segment Tree to get maximum value in a continuous segment of the array in log(N) time.
Brief Working of the Segment Tree
- The segment tree is used for finding maximum and minimum and various operations on a continuous segment of an array in log(N) time. In our case, we want to determine the maximum value of a continuous segment of the sumarr.
- It is a tree where each node contains its children's max(here) value. Refer to the below figure for more understanding. The height of the segment tree is log(N).
- Now let us suppose we have to answer the query a[l… r]. For this, we check if the current node contains the value of [l… r] only. If so, we return the value. If not, we recursively visit the left child and the right child. We note that for each level, we visit a maximum of 4 nodes, and as the height is log(N), the time for each query is maximum 4 x log(N).
Segment Tree for an array [1,21,20,30].
- Here the arr=[1,21,20,30]. The leaves have the value 1,21,20 and 30. The level above the leaves contains the max(1,21) and max(20,30. So their values is 21 and 30. The root node contains max(21,30), i.e. their max of the left and right child. Thus we data of the segment tree is [30, 30, 21, 30, 1, 21, 20, 30]. Here note that the function is max.
Thus the steps of our approach are:
- Store both of the arrays A and B in an array arr(for sorting them based on A)
- Sort them based on A
- Make an variable iterator which keeps the count of the maximum j such that (i+1,i+2, …j) satisfies 0<=A[j]-A[i]<=k
- Make a Segment Tree to find out the maximum value of A[index]+B[index] such that the index belongs to (i+1,i+2, …j).
- Iterate the array and for each i, find the j such that 0<=A[j]-A[i]<=k.
- Find the maximum value for the i, the maximum value will be (B[i] - A[i]) + (B[j]+A[j]) = (B[i] - A[i]) + the maximum value from the Segment Tree = (B[i] - A[i]) + s.query(current+1,iterator1). The s.query(current+1,iterator1) gives the maximum value from the segment (current+1, current+2 ,... iterator1-1) from the sumarr.
- If the value found is greater than the current answer, update the answer.
- Return the answer.
Pseudo Code
DEFINE CLASS SegmentTree:
DEFINE FUNCTION __init__(self, data, default=0, func=max):
"""initialize the segment tree with data"""
SET self._default TO default
SET self._func TO func
SET self._len TO len(data)
SET self._size TO _size TO 1 << (self._len - 1).bit_length()
SET self.data TO [default] * (2 * _size)
SET self.data[_size:_size + self._len] TO data
FOR i IN reversed(range(_size)):
SET self.data[i] TO func(self.data[i + i], self.data[i + i + 1])
DEFINE FUNCTION __delitem__(self, idx):
SET self[idx] TO self._default
DEFINE FUNCTION __getitem__(self, idx):
RETURN self.data[idx + self._size]
DEFINE FUNCTION __setitem__(self, idx, value):
idx += self._size
SET self.data[idx] TO value
idx >>= 1
WHILE idx:
SET self.data[idx] TO self._func(self.data[2 * idx], self.data[2 * idx + 1])
idx >>= 1
DEFINE FUNCTION __len__(self):
RETURN self._len
DEFINE FUNCTION query(self, start, stop):
"""func of data[start, stop)"""
start += self._size
stop += self._size
SET res_left TO res_right TO self._default
WHILE start < stop:
IF start & 1:
SET res_left TO self._func(res_left, self.data[start])
start += 1
IF stop & 1:
stop -= 1
SET res_right TO self._func(self.data[stop], res_right)
start >>= 1
stop >>= 1
RETURN self._func(res_left, res_right)
DEFINE FUNCTION __repr__(self):
RETURN "SegmentTree({0})".format(self.data)
DEFINE FUNCTION maximize(a,b,k):
n=len(a)
arr=[[i,j] FOR i,j IN zip(a,b)]
arr.sort()
a=[i[0] FOR i IN arr]
b=[i[1] FOR i IN arr]
# OUTPUT(arr)
iterator1=0
sumarr=[i+j FOR i,j IN zip(a,b)]
s=SegmentTree(sumarr,float("-inf"),max)
answer=float("-inf")
FOR current IN range(n):
WHILE iterator1<n and a[iterator1]-a[current]<=k:
# we increase the iterator UNTIL the condition of k is satisfied
iterator1+=1
# OUTPUT(current,s)
# we update the answer with best value .
# OUTPUT(current,a[current],b[current])
IF iterator1-current-1>0:
answer=max(answer,b[current]-a[current]+s.query(current+1,iterator1))
IF answer==float("-inf"):
# IF answer was not updated then it was not found thus we RETURN -1
RETURN -1
RETURN answer
A=[1,10,20,30]
B=[4,5,3,7]
K=11
ans=maximize(A,B,K)
OUTPUT(ans)
Python3 Implementation
class SegmentTree:
def __init__(self, data, default=0, func=max):
"""initialize the segment tree with data"""
self._default = default
self._func = func
self._len = len(data)
self._size = _size = 1 << (self._len - 1).bit_length()
self.data = [default] * (2 * _size)
self.data[_size:_size + self._len] = data
for i in reversed(range(_size)):
self.data[i] = func(self.data[i + i], self.data[i + i + 1])
def __delitem__(self, idx):
self[idx] = self._default
def __getitem__(self, idx):
return self.data[idx + self._size]
def __setitem__(self, idx, value):
idx += self._size
self.data[idx] = value
idx >>= 1
while idx:
self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
idx >>= 1
def __len__(self):
return self._len
def query(self, start, stop):
"""func of data[start, stop)"""
start += self._size
stop += self._size
res_left = res_right = self._default
while start < stop:
if start & 1:
res_left = self._func(res_left, self.data[start])
start += 1
if stop & 1:
stop -= 1
res_right = self._func(self.data[stop], res_right)
start >>= 1
stop >>= 1
return self._func(res_left, res_right)
def __repr__(self):
return "SegmentTree({0})".format(self.data)
def maximize(a,b,k):
n=len(a)
arr=[[i,j] for i,j in zip(a,b)]
arr.sort()
a=[i[0] for i in arr]
b=[i[1] for i in arr]
# print(arr)
iterator1=0
sumarr=[i+j for i,j in zip(a,b)]
s=SegmentTree(sumarr,float("-inf"),max)
answer=float("-inf")
for current in range(n):
while iterator1<n and a[iterator1]-a[current]<=k:
# we increase the iterator until the condition of k is satisfied
iterator1+=1
# print(current,s)
# we update the answer with best value .
# print(current,a[current],b[current])
if iterator1-current-1>0:
answer=max(answer,b[current]-a[current]+s.query(current+1,iterator1))
if answer==float("-inf"):
# if answer was not updated then it was not found thus we return -1
return -1
return answer
A=[1,21,20,30]
B=[4,5,19,18]
K=5
ans=maximize(A,B,K)
print(ans) # 25
Input
A=[1,21,20,30]
B=[4,5,19,18]
K=5
Output:
25
Time Complexity
The time complexity for the above program is O(N x log(N)), where N is the Arrays A and B size.
Making the array arr from A and B takes O(N) time. Then sorting it takes O(N x log(N)) time.
We are also making a Segment Tree of the arr sumarr. Building the segment tree takes O(N) time. But the query in the Segment Tree takes log(N) time. Since we ask for N queries, the time complexity for all the queries in O(N x log(N)) time.
Space Complexity
The space complexity of the above code is O(N).
We are making an array arr from array A and array B containing 2xN elements.
Again we make sumarr that contains O(N) elements.
The Segment Tree also contains O(N) elements. As all the arrays contain O(N) elements, the space complexity of the program is O(N).
FAQs
-
What is the brute force method, and what is its time complexity?
In the brute force approach we check for every (i,j) pair and find the pair having maximum value B[i]+B[j] + abs(A[i]-A[j]). Thus the time complexity will be O(NxN).
-
What is its space complexity in the naive approach?
The extra space complexity will be O(1) as we would only have one variable to store the answer. However, the input array contains N elements, so the space complexity is O(N).
-
What is the use of Segment Tree in the code?
Using a Segment Tree, we can add, delete and find the maximum element in approximate log(N) time where N is the size of the Segment Tree.
-
What are the other methods in which we could have found the maximum element quickly?
We could have found the maximum element quickly using a range query. We want to find the maximum element among a continuous segment of array, we could have used a range query.
-
What is a Segment Tree?
A segment tree is a tree data structure used for storing a piece of particular information about segments or intervals of an array which we can query at any point in time.
Key Takeaways
In this article, we first learnt how to simplify a given condition. Then we used an application of Segment Tree to find out the maximum value on a segment of an array.
This is one of the widely popular applications of the Segment Tree.
If you want to learn segment trees from scratch, then do check out this amazing tutorial.
Some of the questions based on applications of the segment tree, which you must solve -
To practice more problems based on the segment tree, you can check out - Segment Tree Archives
Check out Coding Ninjas Studio to learn more about competitive programming, DSA, attempt mock tests, interview preparation and much more.
Happy Learning!!!
39+ registered 