# Calculate the Z-array

## Task

Given a list of numbers $X$ produce a second list of numbers $Y$ such that $Y_i$ is the length of the longest common prefix of $X$ and $X$ with the first $i$ elements removed.

For example if the input is

```
[1,2,2,1,1,2,1,2,2,1,2,1]
```

The output should be

```
[12,0,0,1,2,0,4,0,0,2,0,1]
```

- The first value is 12 since the longest common prefix of the list with itself is the entire list, which is 12 long.
- The second value of the output is 0, since the second value of the input is 2 and the input does not start with 2.
- The third is also 0 for the same reason.
- The fourth value of the output is 1, since the fourth value of the input is 1 and the input starts with 1. However the fifth value of the input is 1 and the second value of the input is 2, these aren't equal so the fourth output can't be greater than 1.
- The fifth value of the output is 2, since from the fifth value on is
`1,2,1`

which matches the first two values of the entire input,`1,2,2`

.

## Scoring

This is code golf so the goal is to minimize the size of your source code as measured in bytes.

I would also like you to include the "Big-O" notation of your algorithm in your answer. There are faster and slower ways to solve the above problem. Scoring should be separated into categories by language and speed, so a fast answer in Kotlin is not competing with a slow answer in Kotlin, just like a slow answer in Python is not competing with a slow answer in C.

## Test cases

```
[1,2,3,4,5] -> [5,0,0,0,0]
[1,1,1,1,1] -> [5,4,3,2,1]
[1,1,1,2,2] -> [5,2,1,0,0]
[1,2,1,2,1] -> [5,0,3,0,1]
[1,2,2,1,2] -> [5,0,0,2,0]
[1,1,1,2,1,1,1,1,2,2] -> [10,2,1,0,3,4,2,1,0,0]
[2,3,1,1,2,3,3,2,3,1] -> [10,0,0,0,2,0,0,3,0,0]
[1,2,9,2,2,1,2,1,3,2] -> [10,0,0,0,0,2,0,1,0,0]
[1,2,9,1,2,1,2,2,1,2] -> [10,0,0,2,0,2,0,0,2,0]
[1,2,3,1,2,3,1,2,3,1,2,3] -> [12,0,0,9,0,0,6,0,0,3,0,0]
[1,2,2,1,1,2,1,2,2,1,2,1] -> [12,0,0,1,2,0,4,0,0,2,0,1]
```

## 1 answer

# JavaScript (Node.js), 86 bytes

```
X=>{Y=[];for(i in X)Y[i]=0,X.slice(i).map((a,b)=>a-X[b]?i='':Y[i]++);return Y.slice``}
```

Using fancy notation, the time complexity is $$\sum^n_{i=1}i$$

...or $O(n^2)$, which according to this is horrible/worst haha.

Definitely can be optimized, but good enough for my standards đź™‚

## 0 comment threads