GoodSequence | Topcoder Archive

Problem Statement

We say that a sequence of integers is good if, for any non-negative integers i and j such that i < j, the number of occurrences of i in any prefix of the sequence is greater than or equal to the number of occurrences of j. A prefix of a sequence is obtained by removing zero or more elements from the end of the sequence.

You are given a int[] a. Return the length of the longest prefix of a that is good. If there is no good prefix, return 0.

Definition

Class:: GoodSequence
Method:: longestGoodPrefix
Parameters:: int[]
Returns:: int
Method signature:: int longestGoodPrefix(int[] a)
(be sure your method is public)

Constraints

a will contain between 1 and 50 elements, inclusive.
Each element of a will be between 0 and 100, inclusive.

Examples

```
{0,1,0,1,2,3,3}
```
```
Returns: 6
```
The sequence prefix {0, 1, 0, 1, 2, 3} is good. However, the whole sequence {0, 1, 0, 1, 2, 3, 3} is not good because 3 occurs two times and 2 occurs only once.
```
{1}
```
```
Returns: 0
```
No prefix of this sequence is good.
```
{0, 2}
```
```
Returns: 1
```
The whole sequence {0, 2} is not good because 2 occurs once, and 1 doesn't occur at all.
```
{0, 1, 3, 2}
```
```
Returns: 2
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.