Divide and Conquer Algorithm Practise [closed]

  algorithm, analysis, c++, python, sorting

Input: A array of unique integers, A, its size n.

Output: Two arrays sl and sr each of size n, containing the ’left scores’ and ’right scores’ of the
elements of A respectively. To be precise: sl[i] will contain the left score and sr[i] the right score
of the element A[i] respectively.

The scores are defined as below:

The left score of the element A[i] is defined as: sl[i] = A[j], where j < i, and A[j] > A[i] and j is
the nearest such index to i. Similarly, the right score of the element A[i] is defined as: sr[i] = A[k],
where k > i, and A[k] > A[i] and k is the nearest such index to i.

If no j exists for an i that satisfies the above condition, then sl[i] = 0. Similarly, if no k ex-
ists for an i that satisfies the above condition, then sr[i] = 0.

It should be easy to work out the O(n
2
) algorithm. Design an O(nlgn) algorithm for this problem.

Source: Windows Questions C++

LEAVE A COMMENT