You are given N counters, initially set to 0, and you have two possible operations on them:

increase(X) − counter X is increased by 1,
max counter − all counters are set to the maximum value of any counter.
A non-empty array A of M integers is given. This array represents consecutive operations:

if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
if A[K] = N + 1 then operation K is max counter.
For example, given integer N = 5 and array A such that:

A = 3
A = 4
A = 4
A = 6
A = 1
A = 4
A = 4
the values of the counters after each consecutive operation will be:

(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)
The goal is to calculate the value of every counter after all operations.

Write a function:

func Solution(N int, A []int) []int

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

The sequence should be returned as:

a structure Results (in C), or
a vector of integers (in C++), or
a record Results (in Pascal), or
an array of integers (in any other programming language).
For example, given:

A = 3
A = 4
A = 4
A = 6
A = 1
A = 4
A = 4
the function should return [3, 2, 2, 4, 2], as explained above.

Assume that:

N and M are integers within the range [1..100,000];
each element of array A is an integer within the range [1..N + 1].
Complexity:

expected worst-case time complexity is O(N+M);
expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Solution: If we do it without thinking of time complexity, we will get a O(N*M) solution. But the problem wants a O(N+M) solution. So first we loop for M, to find all the max ops, and the max value of the last max_op. Taking into account the inc() operations on a same position, to compute thread max (local max)

After that, we loop for the remaining of N, after having initialized the counters to max vals. And just do the counter ops

Code:

package solution

// you can also use imports, for example:
// import “fmt”
// import “os”

// you can write to stdout for debugging purposes, e.g.
// fmt.Println(“this is a debug message”)

func Solution(N int, A []int) []int {
// write your code in Go 1.4

global_max := 0
global_max_pos := -1
my_map := make(map[int]int)
for i, v := range A {
if v <= N {
count, ok := my_map[v]
if !ok {
my_map[v] = 1
}
} else {
tmp := count + 1
my_map[v] = tmp
}
}
} else {
global_max_pos = i
// reset
my_map = make(map[int]int)
}
}

ret := make([]int, N)

for i := 0; i < N; i++ {
ret[i] = global_max
}

for i := global_max_pos + 1; i < len(A); i++ {
ret[A[i]-1]++
}
return ret
}

It works in O(N+M) and scores 100% on codilty.

From → Uncategorized