My problem is quite similar to the question found here, except I am attempting to answer the question in Python.
Given an array of N counters, all initialized to 0, and an array
Arepresenting a series of operations, find the final state of the counters. Each entry in
Ashould be interpreted as follows:
- If 1 ≤
A[k]≤ N, then increase the counter at
A[k]= N + 1, then set all counters to current maximum value.
def solution(N, A): # write your code in Python 2.7 counters =  * N max_count = 0 for x in A: if 1 <= x and x <= N: counters[x-1] += 1 if counters[x-1] > max_count: max_count += 1 else: counters = [max_count] * N return counters
Nothing I can come up with allows me to do this in \$O(N + M)\$ time. I get rid of any
max() functions going through the list by keeping track of it, but for the life of me I don't know how one is supposed to update N different variables M times (worst case scenario) without it being \$O(N * M)\$.
I am asking this question because I am uncertain what this question even asks is possible without having N processors to bring the \$O(N)\$ by itself stage of updating the counter array down to \$O(1)\$ through parallelization. Since the other question hasn't been answered, I guess what I want to know is if there is a data structure or some other heuristic that will get this down to \$O(M + N)\$.