Readme File

Official Big-O Cheat Sheet

Here is the Offical Big-O Sheat Poster:

_images/bigo_cheat.png

Here is the Common Data Structure Operations:

_images/common_data_struct.png

How to calculate the time and space complexity?

The depth of recursion can affect the space, required by an algorithm. Each recursive function call usually needs to allocate some additional memory (for temproary data) to process its argument, so a recursive algorithm will require space O(depth of recursion).

The examples of linear sum algorithm and binary sum algorithm:

def linear_sum(S: List[int], stop: int) -> int:
    """ Using linear recursion to calculate sum of all elements of the array """

    # time:O(N) space:O(N)

    if (stop == 1):
        return S[0]
    else:
        return linear_sum(S, stop-1) + S[stop-1]

def binary_sum(S: List[int], start: int, stop: int) -> int:
    """  Using binary recursion to calculate sum of all elements of array
    Return the sum of the numbers in implicit slice S[start:stop]. """

    # time:O(N) space:O(log n)

    if start >= stop:                      # zero elements in slice
        return 0
    elif start == stop-1:                  # one element in slice
        return S[start]
    else:                                  # two or more elements in slice
        mid = (start + stop) // 2

    return binary_sum(S, start, mid) + binary_sum(S, mid, stop)

The binary sum algorithm uses O(log n) improves over the linear sum algorithm uses O(n).

Solutions list

Leetcode Solutions

#

Title

Level

Time

Space Note

Tags

1

twoSum()

Easy

O(N)

O(N)

HashMap

168

convertToTitle()

Medium

O(log N)

O(log N)

basic

10

isMatch()

Hard

O(NM)

O(NM)

Dynamic Programming

13

romanToInt()

Easy

O(N)

O(log N)

Basic

1239

maxLength()

Medium

O(N)

O(N)

DFS

1192

criticalConnections()

Hard

O(N)

O(N + M)

DFS

565

arrayNesting()

Medium

O(N)

O(1)

Basic

162

findPeakElement()

Medium

O(log N)

O(1)

Binary Search

657

judgeCircle()

Easy

O(N)

O(1)

Basic

1048

longestStrChain()

Medium

O(N^2)

O(N)

Stack

3

lengthOfLongestSubstring()

Medium

O(N)

O(N)

Two Pointers

2260

minimumCardPickup()

Medium

O(N)

O(N)

Two Pointers

547

findCircleNum()

Medium

O(N^2)

O(N^2)

DFS

207

canFinish()

Medium

O(N + M)

O(N + M)

Topological Sorting

300

lengthOfLIS()

Medium

O(N^2)

O(N)

Dynamic Programming

64

minPathSum()

Medium

O(NM)

O(NM)

DFS

34

searchRange()

Medium

O(log N)

O(1)

Stack

53

maxSubArray()

Easy

O(N)

O(1)

Basic

71

simplifyPath()

Medium

O(N)

O(N)

Stack

78

subsets()

Medium

O(N*2^N)

O(N*2^N)

Backtracking

91

numDecodings()

Medium

O(N)

O(N)

Dynamic Programming

1763

longestNiceSubstring()

Easy

O(N* log N)

O(N)

Divide and Conquer

217

containDuplicate()

Easy

O(N)

O(N)

HashMap

283

moveZeroes()

Easy

O(N)

O(1)

Fast and Slow Pointers

36

isValidSudoku()

Medium

O(N^2)

O(N)

BFS

1704

halvesAreAlike()

Easy

O(N)

O(1)

Two Pointers

122

maxProfitII()

Medium

O(N)

O(1)

Basic

121

maxProfit()

Easy

O(N)

O(1)

Dynamic Programming

714

maxProfitwithfee()

Medium

O(N)

O(1)

Dynamic Programming

944

minDeletionSize()

Easy

O(NM)

O(1)

Basic

44

WildcardisMatch()

Hard

O(NM)

O(N)

Dynamic Programming

2280

minimumLines()

Medium

O(N log N)

O(1)

Basic

496

nextGreaterElement()

Easy

O(N + M)

O(M)

Stack

503

nextGreaterElementsII()

Medium

O(N)

O(N)

Stack

739

dailyTemperatures()

Medium

O(N)

O(N)

Stack

2281

totalStrength()

Hard

O(N^2)

O(1)

Basic

100

isSameTree()

Easy

O(N)

O(N)

Tree Node

2134

minSwaps()

Medium

O(N)

O(1)

Sliding Window

1920

buildArray()

Easy

O(N)

O(1)

Basic

1480

runningSum()

Easy

O(N)

O(1)

Basic

215

findKthLargest()

Medium

O(N)

O(1)

Quick Select

973

kClosest()

Medium

O(N log N)

O(1)

Quick Select

15

threeSum()

Medium

O(N^2)

O(N)

Two Pointers

8

myAtoi()

Medium

O(N)

O(1)

Basic

125

isPalindrome()

Easy

O(log N)

O(1)

Two Pointers

9

isPalindromeNum()

Easy

O(log N)

O(1)

Two Pointers

1496

isPathCrossing()

Easy

O(N)

O(N)

HashMap

290

wordPattern()

Easy

O(N)

O(N)

HashMap

58

lengthOfLastWord()

Easy

O(1)

O(N)

Basic

14

longestCommonPrefix()

Easy

O(NM)

O(1)

Basic

373

kSmallestPairs()

Medium

O(N*log N)

O(N)

BFS

704

search()

Easy

O(log N)

O(1)

Binary Search

733

floodFill()

Easy

O(N*M)

O(N*M)

DFS

Sphinx Python Practice

Documentation Status

Introduction

This repository would be useful as a reference for documentation with Python 3 and Sphinx. There is also a short blog post on this on my website.

It is strongly recommended to watch Brandon Rhodes’s Sphinx tutorial session at PyCon 2013 and leimao’s blog post.

Files

.
├── Makefile
├── README.md
├── build
├── doc
│   ├── Makefile
│   ├── README.md
│   ├── __init__.py
│   ├── build
│   ├── make.bat
│   └── source
│       ├── _static
│       ├── _templates
│       ├── api.rst
│       ├── conf.py
│       ├── guide.rst
│       └── index.rst
├── leetcode
│   ├── __init__.py
│   ├── impl
│   │   └── solution.py
│   └── mocktest.py
├── make.bat
├── requirements.txt
└── source
    ├── _static
    ├── _templates
    ├── conf.py
    └── index.rst

Installation

The leetcode folder used for the tutorial has no dependency. But for completeness, we added setuptools and sphinx to our requirements.txt.

To install the dependencies, please run the following command in the terminal.

$ pip install -r requirements.txt

To install the leetcode, which we would not probably do, please run the following command in the terminal.

$ pip install .

Build Documentations

Please check the `README <docs/README.md>`_ in `docs <docs/>`_ for details.

Tips to Improve Skills

When being stuck, there are a few things you can do to give yourself hints:

  1. Look at the tag for the problem and see what kind of algorithm or data structure is needed for solving

  2. Look at the hints provided by Leetcode

  3. Quickly look at the discussion title to see what the expected complexity is or the algorithm.

  4. Estimate the Time Complexity of the problem based on the input constraints.

References