BIG - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: maximus11
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Given an array A, for each index i decide if A_i \gt A_j for all j \lt i.

EXPLANATION:

A_i will be larger than every A_j before it if and only if A_i is larger than the maximum A_j before it.

This means all we need to do is keep a running maximum of the elements from left to right, and compare A_i against this running maximum.
That is,

  • Let \text{mx} = 0 initially.
  • For each i from 1 to N in order:
    • First, check if A_i \gt \text{mx}. If yes, A_i is larger than everything before it.
    • Then, set \text{mx} := \max(\text{mx}, A_i).

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    mx = 0
    ans = [0] * n
    for i in range(n):
        if a[i] > mx:
            mx = a[i]
            ans[i] = 1
    print(*ans)