-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcounter-problem.java
More file actions
87 lines (78 loc) · 2.31 KB
/
Copy pathcounter-problem.java
File metadata and controls
87 lines (78 loc) · 2.31 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//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.
//• Worst-case time complexity is O(N+M)
//• Worst-case space complexity is O(N)
class Solution {
public int[] solution(int N, int[] A) {
// write your code in Java SE 8
int max =0;
int min =0;
int[] counter = new int[N];
int at;
//iterate through array A
for (int i=0; i<A.length; i++){
at=A[i];
if (at>=1 )
{
if( at<=N)
{
if(counter[at-1]<min){
counter[at-1]=min+1;
}
else{
counter[at-1]++;
}
if (counter[at-1]>max){
max++;
}
}
else
{
min=max;
}
}
}
for(int i=0; i<N; i++){
if(counter[i]<min){
counter[i]=min;
}
}
return counter;
}
}
// Below is the obvious solution with:
// Worst case O(N^2) time complexity
// Worst case O(N) space complexity
/* class Solution {
public int[] solution(int N, int[] A) {
// write your code in Java SE 8
int max =0;
int[] counter = new int[N];
int at;
//iterate through array A
for (int i=0; i<A.length; i++){
at=A[i];
if (at>=1 )
{
if( at<=N)
{
counter[at-1]++;
if (counter[at-1]>max){
max++;
}
}
else
{
for(int j=0; j<N; j++){
counter[j]=max;
}
}
}
}
return counter;
}
} */