Skip to content

Must-know competitive programming problems with solutions and intuitive visualizations

Notifications You must be signed in to change notification settings

leduckhai/Awesome-Competitive-Programming

Repository files navigation

Awesome Competitive Programming Problems

Please press ⭐ button if you like this repo. ThαΊ₯y ngon thΓ¬ nhαΊ₯n star ⭐ ủng hα»™ mΓ¬nh nha cΓ‘c Δ‘α»“ng rΓ’m

This repository contains my implementation of useful / well-known data structures, algorithms and solutions for awesome competitive programming problems in Hackerrank, Project Euler and Leetcode

I create this for faster implementation and better preparation in interviews as well as programming contests :trollface: :trollface:

⚠️ This repo is day-by-day updated. Please make sure you have the latest version!

πŸ”₯ New updates today: Longest Substring Without Repeating Characters[Leetcode]

❓ How to use

Overview of the file:

🧨 Tips and Tricks

Here is some tips and tricks to ACE all competitive programming problems and interview questions:

If input array is sorted then
    - Binary search
    - Two pointers

If asked for all permutations/subsets then
    - Backtracking

If given a tree then
    - DFS
    - BFS

If given a graph then
    - DFS
    - BFS

If given a linked list then
    - Two pointers

If recursion is banned then
    - Stack

If must solve in-place then
    - Swap corresponding values
    - Store one or more different values in the same pointer

If asked for maximum/minumum subarray/subset/options then
    - Dynamic programming

If asked for top/least K items then
    - Heap

If asked for common strings then
    - Map
    - Trie

Else
    - Map/Set for O(1) time & O(n) space
    - Sort input for O(nlogn) time and O(1) space

πŸ‰ Data structures, Algorithms and Patterns

A) Data Structures Applications

🌴 Binary Search Tree Algorithm


B) String Algorithm

🌾 Suffix Tree - Suffix Array

    • Longest Palindromic Substring - O(n)
    • Pattern Search - O(log(n))

C) Searching and Graph Algorithms

❄️ Graph Theory

    • Graph Representation using Adjacency List: Weighted, Un-/Directed
    • Find All Nodes: Find All Nodes in the Unweighted Graph - O(V+E) for Adjacency List , V, E is the number of vertices and edges
    • Find All Edges

♻️ Detect Cycle

    • Detect Cycle: Disjoint Set: Detect Cycle in an Undirected Graph based on Disjoint Set (Union-Find) using "Union by Rank and Path Compression" - O(V)

✈️ Graph Traversal

    • Breadth-First Search: Find BFS Path from a Starting Node in Un-/Directed Graph - O(V+E) for Adjacency List; O(V2) for Adjacency Matrix , V, E is the number of vertices and edges
    • Depth-First Search: Find DFS Path from a Starting Node in Un-/Directed Graph - O(V+E) for Adjacency List; O(V2) for Adjacency Matrix , V, E is the number of vertices and edges

☘️ Minimum Spanning Tree (MST)

    • MST: Kruskal Algorithm[PDF]: Find Minimum Spanning Tree (MST) of an Undirected Graph using Kruskal Algorithm - O(E.log(E)) or O(E.log(V))

πŸ›΄ Shortest Path

Type of Algorithm Subjects of Application Time Complexity
Breadth-First Search Unweighted, Un-/Directed Graph O(V+E) for Adjacency List
Dijkstra Non-Negative Un-/Weighted Un-/Directed Graph O(E.log(V)) for Min-priority Queue
Bellman-Ford
Floyd-Warshall
    • Shortest Path: Breadth-First Search: Find the Shortest Path in a Unweighted Un-/Directed Graph based on BFS - O(V+E) for Adjacency List , V, E is the number of vertices and edges
    • Shortest Path: Bellman-Ford
    • Shortest Path: Floyd-Warshall

D) Greedy Algorithm

  1. Sherlock and The Beast
  • Find the "Decent Number" having n Digits ("Decent Number" has its digits to be only 3's and/or 5's; the number of 3's it contains is divisible by 5; the number of 5's it contains is divisible by 3; and it is the largest such number for its length)
  1. Largest Permutation
  • Swap 2 digits of a number k times to get largest number - O(n)

E) Dynamic Programming

Coin Change Algorithms: Given an array of choices, every choice is picked unlimited times

Knapsack Problems: Given an array of choices, every choice is picked only once

πŸ’° Coin Change Algorithms

    • Coin Change[PDF]: How many ways to pay V money using C coins [C1,C2,...Cn] - O(C.V)

πŸ‘œ Knapsack Problems

    • Knapsack 0/1[Wiki]: Given a List of Weights associated with their Values, find the Founding Weights and Maximum Total Value attained with its Total Weight <= Given Total Weight, each Weight is only picked once (0/1 Rule) - O(N.W) , N, W is length of weights array and given total weight
    • Partition Problem: Subset Sum[Wiki]: Given an Array containing only Positive Integers, find if it can be Partitioned into 2 Subsets having Sum of elements in both subsets is Equal. - O(N.T) , N, T is the length of numbers array and the target sum (=sum/2)
    • Partition Problem: Multiway Number Partitioning[Wiki]:

πŸ“ˆ Path Sum Problems

Subsequence = Any subset of an array/string

Subarray = Contiguous subsequence of an array

Substring = Contiguous subsequence of a string

πŸ“… Subarray Problems

🍑 Subsequence Problems

πŸ“ƒ Substring Problems


F) Two Pointers - Sliding Window

πŸ“– Non-categorized


G) Mathematics

πŸ“˜ Binomial Coefficient Problems

    • Pascal Triangle: Create Pascal Triangle (to Calculate Multiple Large-Number Combinations) - O(n2)
    • PE #15: Lattice Paths[PDF] : Find the number of routes from the top left corner to the bottom right corner in a rectangular grid

πŸ“• Factors Problems

πŸ“— Multiples Problems

πŸ““ Permutation Problems

    • Permutation Check: Check if 2 Numbers/Strings are Permutations - O(n) , n = max(|a|,|b|)

πŸ“™ Primes Problems

πŸ“” Primes-Factors Problems

    • Euler Totient Function (Number List): Find ALL Numbers of Coprimes < n based on Euler Totient Function - O((l) + m.loglogm + l.(logm + k)) , k is the number of prime factors of n; m and l is max value and length of the input number list

πŸ“’ Pythagorean Theorem

πŸ“– Non-categorized


H) Linked List

🐍 Singly-linked List

Problem statement: Do something on a given singly-linked List

Hints:

  1. Simply convert linked list to 1D array and solve on the array using "ListNode_to_Array"
  2. If necessary, convert 1D array back to the linked list using "Array_to_ListNode"
    • List Node: Create a Singly-linked List using "Node class"
    • ListNode to Array: Convert ListNode into Array, could be used as print to "see" inside a ListNode - O(n)

I) Matrix

πŸ’» Matrix x Simulation

Problem statement: Move current position within the matrix along diagonals, up-down-right-left, ...

Hints:

  1. Use variable flag = 'up' or 'down' ... to guide the current position to the next position
if flag == 'up':
  # Do something
  # Consider to change the flag = 'down' or 'right' or 'something'
  1. Pay attention to the matrix boundary when moving
def inMatrix(r,c):
  # R, C is the matrix size
  # r, c is current position
  if r >= 0 and c >= 0 and r < R and c < C:
    return True
  else:
    return False
  1. Use variable seen = set() to not move to the seen position or to not start as a current position
if (r,c) not in seen:
  # Do something

Matrix x Graph


Recursion Algorithm

Backtracking

Divide and Conquer