dsa

Frequently used Python gists in competitive programming

A collection of frequently used python gists

Converting data types

Get binary equivalent of integer

The bin() method converts and returns the binary equivalent string of a given integer.

​

Get integer when dividing float

a = num//div

​

Array

Initialise an array of n length

Initialise an array of n length with 0: arr = [0] * n

​

Initialise a two-dimensional array

Don’t use [[v]*n]*n, it is a trap!

>>> a = [[0]*3]*3
>>> a
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
>>> a[0][0]=1
>>> a
[[1, 0, 0], [1, 0, 0], [1, 0, 0]]

but t = [ [0]*3 for i in range(3)]

works great.

​

Get Value at Index

To handle array indices in case INF needs to be handled

def get_value_at_index(arr, i):
    if i >= 0:
        if i < len(arr):
            return arr[i]
        else:
            return float("inf")
    else:
        return -float("inf")

​

Custom comparison between two objects

import functools

def mycmp(a, b):
  print("comparing ", a, " and ", b)
  if a > b:
      return 1
  elif a < b:
      return -1
  else:
      return 0

print(min([45, 78, 813], key=functools.cmp_to_key(mycmp)))
print(max([45, 78, 813], key=functools.cmp_to_key(mycmp)))

Eg:
Given a list of numbers in string format, you want to construct the biggest number out of it ["99", "990"]
Solution is to sort in decreasing order and append the numbers, but python’s sort won’t work for the above case

​

Custom max

Using lambda:

lis = ['1','100','111','2', 2, 2.57]
max(lis, key=lambda x: int(x))

Using

test = [1, 2, 3, 4, 2, 2, 3, 1, 4, 4, 4]
print(max(set(test), key=test.count))

​

Reverse array or string

  • Reverse a string: a[::-1]
  • Reverse partial string: a[2:4] = a[2:4][::-1]

​

Repeat string n times

Repeat string x n times: x*n

​

stdin / stdout

# ends the output with a <space> 
print("Hello World", end=' ')

​

Read input from stdin

# Read comma separated integers from stdin
# 3,4,-1 , 4,5
arr = list(map(int, input().split(',')))

​