Recreate a O(n*k) algorithm to Θ(n)

Question

You have 2 int[] arrays with same length on input - x, k.

Each element in array x tells you the power level of the given index.

Each element in array k tells you the number of power levels to choose from array x(including itself).

These are the conditions for the arrays: (∀i ∈ {1, . . . , n − 1})(1 ≤ ki+1 ≤ ki + 1) Try to return index (j) of the most powerful index for each group in x defined by ki. xj =max{xs |i−ki <s≤i} with time-complexity Θ(n) where n is the length of the arrays.

I've made a naive solution that is O(n*k) where k represents the use of max() to find the max number in each subarray:

"""
    (∀i ∈ {1, . . . , n − 1})(1 ≤ ki+1 ≤ ki + 1)
    max{xs |i−ki < s ≤ i}
"""
x = [1000, 4, 3, 2, 500, 10, 1]
k = [1, 2, 2, 3, 2, 3, 1]

for i in range(len(x)):
    group = max(x[i - k[i] + 1 : i - k[i] + 1 + k[i]])
    print(x.index(group), end=" ")

Correct output for the input in the code block is: 0 0 1 1 4 4 6

x1 -> k1 == 1: we are only choosing from x1(1000) -> in that case we return the first index
x2 -> k2 == 2: we are choosing from x1, x2(1000, 4) -> first index is larger so we return it
x3 -> k3 == 2: x2, x3 -> second index is the largest
x4 -> k4 == 3: x2, x3, x4 -> second index is the largest
x5 -> k5 == 2: x4, x5
x6 -> k6 == 3: x4, x5, x6
x7 -> k7 == 1: x7

Maybe it could be done with queue??

Answer 1

It's challenging to assert that accessing the maximum of a sublist in O(1) is feasible when the input for the array k is typically treated as variable. Your situation is the range max query problem, where enhancing query time might involve accessing the maximum in a sublist in O(log n) which gives you an overall of O(k*log(n)) worst case scenario. Refer to segment tree ressources to understand the range query problems.

For implementing a solution using a segment tree for your problem, you can refer to this link: Range Range Max Query Problem