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