Python Basics

String

1
s = s[::1] # reverse string, O(1)

Stack

1
2
3
s = []
s.append(1)
s.pop()

Dictionary

1
2
3
4
5
6
7
8
9
d = dict()
d[key] = d.get(key, 0) + 1

d = collections.OrderedDict()
d[key] = val
val = d.pop(key)

# pop least used key
d.popitem(last=False)

Queue

https://note.nkmk.me/en/python-collections-deque/

1
2
3
4
5
6
q = deque()
q.append("a")
where q:
	curr = q.popleft()

q.extendleft([1,2,3,4]) # give [4,3,2,1]

Sort

1

bisect.bisect(a, x, lo=0, hi=len(a))
Similar to bisect_left(), but returns an insertion point which comes after (to the right of) any existing entries of x in a.

1
2
a = [1,2,3,4,5]
ind = bisect.bisect(a, 0) # gives 0
1
2
points = sorted(points, key=lambda x: x[0]**2 + x[1]**2)
intervals.sort(key=lambda x: x[0])

Heap

1
2
3
4
5
6
7
8
def heapsort(iterable):
	h = []
	for value in iterable:
		heappush(h, value)
	return [heappop(h) for i in range(len(h))]

count = Counter(nums)
heapq.nlargest(k, count.keys(), key=count.get)

Quicksort, $O(n\log n)$

1
2
3
4
5
6
7
8
def quicksort_recursive(a):
    if len(a) == 0:
        return a
    p = len(a) // 2
    l = [i for i in a if i < a[p]]
    m = [i for i in a if i == a[p]]
    r = [i for i in a if i > a[p]]
    return quicksort_recursive(l) + m + quicksort_recursive(r)

Mergesort, $O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# MergeSort in Python


def mergeSort(array):
    if len(array) > 1:

        #  r is the point where the array is divided into two subarrays
        r = len(array)//2
        L = array[:r]
        M = array[r:]

        # Sort the two halves
        mergeSort(L)
        mergeSort(M)

        i = j = k = 0

        # Until we reach either end of either L or M, pick larger among
        # elements L and M and place them in the correct position at A[p..r]
        while i < len(L) and j < len(M):
            if L[i] < M[j]:
                array[k] = L[i]
                i += 1
            else:
                array[k] = M[j]
                j += 1
            k += 1

        # When we run out of elements in either L or M,
        # pick up the remaining elements and put in A[p..r]
        while i < len(L):
            array[k] = L[i]
            i += 1
            k += 1

        while j < len(M):
            array[k] = M[j]
            j += 1
            k += 1


# Print the array
def printList(array):
    for i in range(len(array)):
        print(array[i], end=" ")
    print()


# Driver program
if __name__ == '__main__':
    array = [6, 5, 12, 10, 9, 1]

    mergeSort(array)

    print("Sorted array is: ")
    printList(array)

Insertion sort, $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Insertion sort in Python


def insertionSort(array):

    for step in range(1, len(array)):
        key = array[step]
        j = step - 1
        
        # Compare key with each element on the left of it until an element smaller than it is found
        # For descending order, change key<array[j] to key>array[j].        
        while j >= 0 and key < array[j]:
            array[j + 1] = array[j]
            j = j - 1
        
        # Place key at after the element just smaller than it.
        array[j + 1] = key


data = [9, 5, 1, 4, 3]
insertionSort(data)
print('Sorted Array in Ascending Order:')
print(data)

Bubble sort, $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Bubble sort in Python

def bubbleSort(array):
    
  # loop to access each array element
  for i in range(len(array)):

    # loop to compare array elements
    for j in range(0, len(array) - i - 1):

      # compare two adjacent elements
      # change > to < to sort in descending order
      if array[j] > array[j + 1]:

        # swapping elements if elements
        # are not in the intended order
        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp


data = [-2, 45, 0, 11, -9]

bubbleSort(data)

print('Sorted Array in Ascending Order:')
print(data)

Selection sort, $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Selection sort in Python


def selectionSort(array, size):
   
    for step in range(size):
        min_idx = step

        for i in range(step + 1, size):
         
            # to sort in descending order, change > to < in this line
            # select the minimum element in each loop
            if array[i] < array[min_idx]:
                min_idx = i
         
        # put min at the correct position
        (array[step], array[min_idx]) = (array[min_idx], array[step])


data = [-2, 45, 0, 11, -9]
size = len(data)
selectionSort(data, size)
print('Sorted Array in Ascending Order:')
print(data)

Array

1
2
arr.reverse() # in-place reverse
deep_copy = arr[:]

Counter

1
2
3
4
5
6
count = Counter(nums).items()
        for k, v in count:
            if v > max_count:
                max_count = v
                maj = k
        return maj