Note: this post is being updated progressively.

1. Sliding window

Problem: Given a string s, find the length of the longest substring without repeating characters.

C#

Runtime: 84 ms, faster than 80.08% of C# online submissions for Longest Substring Without Repeating Characters.
Time Complexity : O(n)
Space Complexity: O(n)

Python 3

Runtime: 64 ms, faster than 65.71% of Python3 online submissions for Longest Substring Without Repeating Characters.
Time Complexity : O(n)
Space Complexity: O(n)

2. Two pointers

Problem: Container With Most Water.

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

C#

Runtime: 176 ms, faster than 99.42% of C# online submissions for Container With Most Water.
Time Complexity = O(n)
Space Complexity = O(1)

Python 3

Runtime: 748 ms, faster than 56.75% of Python3 online submissions for Container With Most Water.
Time Complexity = O(n)
Space Complexity = O(1)

3. Fast and Slow Pointers (Hare and Tortoise algorithm)

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Notice that you should not modify the linked list.

C#

Runtime: 96 ms, faster than 77.01% of C# online submissions for Linked List Cycle II.
Time complexity: O(N)
Space complexity: O(1)

Python 3

Runtime: 48 ms, faster than 81.20% of Python3 online submissions for Linked List Cycle II.

4. Merge intervals

c#

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Runtime: 248 ms, faster than 96.73% of C# online submissions for Merge Intervals.
Time Complexity: O(n.log(n))
Space Complexity O(log(n))

Python 3

Runtime: 88 ms, faster than 52.59% of Python3 online submissions for Merge Intervals.

5. Cyclic Sort

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

C#

Runtime: 304 ms, faster than 72.55% of C# online submissions for Find All Duplicates in an Array.
Time complexity: O(N)
Space complexity: O(1)

Python 3

Runtime: 365 ms, faster than 50.56% of Python3 online submissions for Find All Duplicates in an Array.

5. In-place reversal of a linked list

C#

Runtime: 76 ms, faster than 99.86% of C# online submissions for Reverse Linked List II.
Time Complexity: O(n)
Space Complexity: O(1)

Python 3

Runtime: 32 ms, faster than 60.16% of Python3 online submissions for Reverse Linked List II.

7. Tree BFS

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

C#

Runtime: 240 ms, faster than 75.21% of C# online submissions for Binary Tree Zigzag Level Order Traversal.
Time complexity O(n)
Space complexity O(1)

Python 3

Runtime: 28 ms, faster than 88.64% of Python3 online submissions for Binary Tree Zigzag Level Order Traversal.

8. Tree DFS

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path’s sum equals targetSum.

A leaf is a node with no children.

c#

Runtime: 248 ms, faster than 61.07% of C# online submissions for Path Sum II.
Time complexity: O(n)
Space complexity: O(log(n))

Python 3

Runtime: 36 ms, faster than 97.15% of Python3 online submissions for Path Sum II.

9. Two heaps

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

• For example, for arr = [2,3,4], the median is 3.
• For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void addNum(int num) adds the integer num from the data stream to the data structure.
• double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

C#

Doesn’t offer PriorityQueue built-in class.

Java

Python 3

Runtime: 508 ms.
Time complexity: O(log(n))
Space complexity: O(1)

10. Subsets

Given a string s, we can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. You can return the output in any order.

Example 1:

Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

BFS Solution:

C#

Runtime: 252 ms
Time Complexity: O(n*m) // n the length of the string, m is the size of the queue
Space Complexity: O(n+m)

Python

Runtime: 52 ms

11. Binary Search

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Follow up: Your solution should run in O(log n) time and O(1) space.

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

C#

Runtime: 100 ms
Time complexity: O(n)
Space complexity: O(1)

Python 3

Runtime: 64 ms

12. Top K elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

C#

Runtime: 252 ms
Time complexity: O(n)
Space complexity: O(1) 

Python 3

Runtime: 104 ms

Solution 2

13. Merge K lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

C#

Runtime: 132 ms

Python 3

Time complexity: O (Nlogk) where k is the number of linked lists.
Space complexity O(1)

14. Topological sort

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: 
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

c#

Runtime: 144 ms
Time complexity: O(n)
Space complexity: O(1)

Python 3

Runtime: 380 ms