Python Gotchas:

Range

The range() function defaults to 0 as a starting value.

Note that range(6) is not the values of 0 to 6, but the values 0 to 5.

Increment the sequence with 3 (default is 1):

for x in range(2, 30, 3):
  print(x)

Multi dimensional arrays

For arbitrary length lists, you can use [ [] for _ in range(N) ] Do not use [ [] ] * N, as that will result in the list containing the same list object N times E.g.

>>> A = [[None] * 2] * 3 # DO NOT USE THIS
>>> A[0][0] = 5
>>> A
[[5, None], [5, None], [5, None]]

https://docs.python.org/2/faq/programming.html#how-do-i-create-a-multidimensional-list

intialize 2d array

m = 4 # row n = 5 # column

dp = [[-1 for _ in range(n)] for _ in range(m)] print(dp)

List.append() returns None

To append and then use the expression: expr = [] expr.append('a') # returns None use the expr

join

>>>sentence = ["abc", "def", "ghij"]
>>>separator = ', '
s = ','.join(sentence)
abc,def,ghij

@lru_cache

Can be used for memoization ! Note that if used with self then GC is not going to remove the instances ever Use only on methods which are static are outside of class

deque

can be used for queue

queue = deque()
queue.append(elem)
elem = queue.popleft() # FIFO

Priority queue also know as heapq - e.q. min heap

https://docs.python.org/3/library/html

Heaps are binary trees for which every parent node has a value less than or equal to any of its children.

>>> h = []

# Heap elements can be tuples. This is useful for assigning comparison values (such as task priorities) alongside the main record being tracked:
>>> heappush(h, (5, 'write code')) # Push O(logn)
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> priority_queue[0] # access Top Element O(1)
>>> heappop(h) # removes the top element of list #Pop Element O(logn)
(1, 'write spec')

heapify(l) # - can create heap from list O(n) https://stackoverflow.com/a/18295327

Max heap

use the same as min heap, just multiply everything by -1

>>> h = []

# Heap elements can be tuples. This is useful for assigning comparison values (such as task priorities) alongside the main record being tracked:
>>> heappush(h, (-1 * 5, 'write code')) # Push O(logn)
>>> heappush(h, (-1 * 7, 'release product'))
>>> heappush(h, (-1 *1, 'write spec'))
>>> heappush(h, (-1 * 3, 'create tests'))
>>> -1 * priority_queue[0] # access Top Element O(1)
>>> -1 * heappop(h) # removes the top element of list #Pop Element O(logn)
(1, 'write spec')

heapify(l) # - can create heap from list O(n) https://stackoverflow.com/a/18295327

heapq and tuples - it compare all the "int" parts of tuple, but not a tuple in tuple

heappush(h, (1,2,3))
heappush(h, (1,1,3))
heappop(h)
(1, 1, 3)
heappush(h, (1,1,3))
heappush(h, (1,1,2))
heappush(h, (1,1,4))
heappop(h)
(1, 1, 2)


heappush(h, (1,1,1,(1,2,3)))
heappush(h, (1,1,2,(1,1,3)))
heappop(h)
(1, 1, 1, (1, 2, 3))
heappush(h, (1,1,1,(1,2,3)))
heappush(h, (1,1,0,(10,1,3)))
heappop(h)
(1, 1, 0, (10, 1, 3))

Set initialization

# set of tuples
# this is a set initialization
seen = {(0,0)}

Char to int value

convert char to in - ord() https://stackoverflow.com/questions/227459/how-to-get-the-ascii-value-of-a-character ord('a')

Tuple from list

tuple(list)

Reverse list

[::-1]

Random

random.randint(0, 10)
random.choice([1,2,3,4])

Building and concatenating strings

s = "".join(['a','b', 'c']) # this is the fastest method

Replace character in python

Strings are immutable in python so the following operation will not work. str1 = “test”; str1[idx] = ‘c’

str1 = "test"
idx = 1
character = 'c'
str1 = str1[:idx] + character + str1[idx+1:]
print(str1)

python slicing https://stackoverflow.com/questions/509211/understanding-slicing

a[start:stop]  # items start through stop-1
a[start:]      # items start through the rest of the array
a[:stop]       # items from the beginning through stop-1
a[:]           # a copy of the whole array
a[start:stop:step] # start through not past stop, by step

# negative number, which means it counts from the end of the array
a[-1]    # last item in the array
a[-2:]   # last two items in the array
a[:-2]   # everything except the last two items

# Similarly, step may be a negative number:
a[::-1]    # all items in the array, reversed
a[1::-1]   # the first two items, reversed
a[:-3:-1]  # the last two items, reversed
a[-3::-1]  # everything except the last two items, reversed

python slicing assignments

nums = [1, 2, 3, 4, 5]

nums[:1] = [6]        # [6, 2, 3, 4, 5]   (replace elements 0 through 1)
nums[1:3] = [7, 8]    # [6, 7, 8, 4, 5]   (replace elements 1 through 3)
nums[-2:] = [9, 0]    # [6, 7, 8, 9, 0]   (replace the last 2 elements)

# changing the length 
## removing
nums = [1, 2, 3, 4, 5]

nums[1:4] = [6, 7]    # [1, 6, 7, 5]        (replace 3 elements with 2)
nums[-1:] = [8, 9, 0] # [1, 6, 7, 8, 9, 0]  (replace 1 element with 3)
nums[:1] = []         # [6, 7, 8, 9, 0]     (replace 1 element with 0)

## adding
nums = [1, 2, 3, 4, 5]

nums[2:2] = [6, 7]    # [1, 2, 6, 7, 3, 4, 5]   (insert 2 elements)
nums[7:] = [8, 9]     # [1, 2, 6, 7, 3, 4, 5, 8, 9] (append 2 elements)
nums[:0] = [0]        # [0, 1, 2, 6, 7, 3, 4, 5, 8, 9] (prepend 1 element)
nums[:] = [ 4, 2]     # [4, 2]         (replace whole list with a new one)

# using steps
nums = [1, 2, 3, 4, 5]

nums[2:5:2] = [6, 7]  # [1, 2, 6, 4, 7] (replace every 2nd element, 2 through 5)
nums[2:5:2] = [6, 7, 8] # Throws a ValueError (can't replace 2 elements with 3)
nums[1::-1] = [9, 0]  # [0, 9, 6, 4, 7] (reverse replace, 1 through start)

INT_MAX and INT_MIN in Python

	print(float('inf'))
	print(float('-inf'))

datastructures python

https://leetcode.com/discuss/study-guide/2713266/Python-Data-Structure-Guide-(Side-by-Side-Comparison-with-C%2B%2B) https://colab.research.google.com/drive/1lqFQ3vyaw3QKQn7QdazE3YRBvQkgzbTa?usp=sharing#scrollTo=3j7Fk5uhwYfS

How do I round a floating point number up to a certain decimal place?

import math
v = 2.35776796976

print(int(v*102)/102)  # 2.35

print(math.ceil(v*102)/102)  # -> 2.36

print(math.floor(v*1000)/1000)  # -> 2.35


import math
# floor
a = 5.67

print(f"Floor of {a}: {math.floor(a)}")
print(f"Ceil of {a} : {math.ceil(a)}")

# gcp of two number (math.gcd(a,b))
a = 2
b = 6

print(f"\nGCD of ({a},{b}) is {math.gcd(a,b)}")

# bin used to represent number in binary
b = 6
print(f"Binary representation of {b}: {bin(b)}")

"""
Output:
Floor of 5.67: 5
Ceil of 5.67 : 6

GCD of (2,6) is 2
Binary representation of 6: 0b110
"""

Taking Input in python

# single input 
a = input()
print(a)

# more than one input

x, y = input("Enter Two numbers: ").split()
print(f"Entered numbers are {x} {y}")

# taking multiple inputs at a time with type casting
input_list = [int(a) for a in input("Enter multiple values: ").split()]
print("list is: ", input_list)

2. SortedDict

Java has a TreeMap for this. https://leetcode.com/discuss/study-guide/1515408/using-python3-sorteddict-effectively-floor-ceillings-minimum-maximum-etc In C++ we have map which stores the key in sorted order likewise we have sorted dict in python ( python dict will be same as unordered map)

# sorted dict is not built in
# Sorted Dict in python
from sortedcontainers import SortedDict

# time complexity for operations is O(logn) => internally uses red black tree
d = SortedDict()
d[2] = 3
d[1] = 4
d[5] = 7
d[6] = 8


dict_item = d.peekitem(len(d)-1) # returns tuple (key, value)
key, value = dict_item[0], dict_item[1]


# items key are in sorted order
print(d)

# get last item of sorted dict
print(f"\n Last Item of sorted dict:  key-> {key} value-> {value}")

# find the upper bound or lower bound of some key
print(d.peekitem(d.bisect_left(5))) # returns the idx after that we can use peekitem
print(d.peekitem(d.bisect_right(5)))

Apply an operation to each element in array and return iterator

map

How to use stack in the python

appends and pops from the end of list are fast https://docs.python.org/3/tutorial/datastructures.html#using-lists-as-stacks

stack = [3, 4, 5]

stack.append(6)

stack.append(7)

stack

copy 2d array

https://stackoverflow.com/questions/6532881/how-to-make-a-copy-of-a-2d-array-in-python

y = [row[:] for row in grid ] # copy 2d array

string operations

parts = s.split("@") s1 = parts[0].replace(".", "")

Sort by value or lambda

sorted_indexes = sorted(range(len(arr)), key=lambda x: arr[x])

Get or default from dict

fruit.get("index", 0) # gets or returns 0

Remove element from dict

del basket[fuirts[left]]

Default for dictionary

https://docs.python.org/3/library/collections.html#defaultdict-examples

s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]

d = defaultdict(list)
for k, v in s:
    d[k].append(v)

sorted(d.items())
[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]