# Posts tagged as “hard”

Problem:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

Example 2:

Idea:

Binary Search

Time complexity: O(log(min(n1,n2)))

Space complexity: O(1)

# Related Problem:

Problem:

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Idea:

count by slope

Time complexity: O(n^2)

Space complexity: O(n)

# Solution:

## C++ / long

Problem:

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

Return 6.

Idea:

Recursion

Time complexity O(n)

Space complexity O(h)

# Solution: Recursion

## Python3

Related Problems:

Problem:

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Idea:

Hashtable / Hashset

Time complexity: O(n)

Space complexity: O(n)

Solution 1: C++ / online

Solution 2: C++ / offline

Problem:

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

Return

Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Idea:

BFS to construct the graph + DFS to extract the paths

Solutions:

C++, BFS 1

C++ / BFS 2

C++ / Bidirectional BFS

Mission News Theme by Compete Themes.