# list index complement

Using a list index complement is a sign of a mature and experienced developer. The complement of `x`

, i.e the tilde `~x`

is `-x -1`

.

```
1 x. -x-1 ~x
2 --------------------------
3 0 -0-1 -1
4 1 -1-1 -2
5 2 -2-1 -3
6 3 -3-1 -4
7 4 -4-1 -5
```

It so happens, that lists (and tuples) in Python can use negative indices, too. i.e the list:

```
1 0 1 2 3 4 5 6 7 8 9
```

Can also be indexed as:

```
1 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1
```

i.e `-1`

refers to the **last** item in the list. `-2`

refers to the **first to last** item.

## Practical example: Palindromicity

A practical algorithmic application of the list index compliment is palindromicity checking.

```
1 def is_palindrome(s):
2 for i in range(len(s)//2):
3 if s[i] != s[~i]:
4 return False
```

## Practical example: Product of Array Except Self

Let's take a look at another practical use of the `~`

list index complement in this classic problem:

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Note: Please solve it without division and in O(n).

Let's work with the following input list:

`2, 3, 4`

The output would be:

`3*4, 2*4, 2*3`

or

`12, 8, 6`

A solution to this problem, is to take the accumulated product of all the numbers from both directions.

The product of these numbers, from the left is:

`2, 2*3, 2*3*4`

or

`2, 6, 24`

The product of these numbers, from the right is:

`24, 12, 4`

or

`2*3*4, 3*4, 4`

But remember we need the product of the numbers, except self. So let's insert a `1`

at the start of this computation, and ignore the last computation.

```
1 1, 2, 2*3 # from the left
2 4*3, 4, 1 # from the right
```

Now taking the product of these two computations, we get:

`3*4, 2*4, 2*3`

In other words, the desired solution.

```
1 A = [2,3,4]
2 left = 1
3 for i in range(len(A)):
4 print(left, end=' ')
5 left *= A[i]
6
7 # output: 1, 2, 6
```

Notice we are printing the value before the `*=`

, which makes sure the first value is the identity. Likewise, we can do the same thing from the right:

```
1 A = [2,3,4]
2 right = 1
3 out = []
4 for i in range(len(A)):
5 out.append(right)
6 right *= A[~i]
7 print(list(reversed(out)))
8
9 # output: [12, 4, 1]
```

In the code above, i flipped the values, because i would like to you think from right to left: i'd like you to break out of your culture-sensitive habit of thinking from left to right only.

Putting these computations together, we get:

```
1 A = [2,3,4]
2 left, right = 1, 1
3 for i in range(len(A)):
4 left *= A[i]
5 right *= A[~i]
```

Our last step is to take the product of these two numbers.

```
1 def product_except_self(A):
2 left, right = 1, 1
3 out = [1] * len(A)
4 for i in range(len(A)):
5 out[i] *= left
6 out[~i] *= right
7 left *= A[i]
8 right *= A[~i]
9
10 print(product_except_self([2,3,4]))
11
12 # Output:
13 # 12, 8, 6
```