Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Example 2:

Idea:

Binary search

Solution:

C++

Time complexity: O(log(num))

Space complexity: O(1)

Problem:

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Example 2:

Solution:

C++

Problem:

In a given integer array nums, there is always exactly one largest element.

Find whether the largest element in the array is at least twice as much as every other number in the array.

If it is, return the index of the largest element, otherwise return -1.

Example 1:

Example 2:

Note:

1. nums will have a length in the range [1, 50].
2. Every nums[i] will be an integer in the range [0, 99].

Solution:

C++

Problem:

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution 1: DFS

Solution 2:  BFS

## Python

• < 10: O(n!) permutation
• < 15: O(2^n) combination
• < 50: O(n^4) DP
• < 200: O(n^3) DP, all pairs shortest path
• < 1,000: O(n^2) DP, all pairs, dense graph
• < 1,000,000: O(nlogn), sorting-based (greedy), heap, divide & conquer
• < 1,000,000: O(n), DP, graph traversal / topological sorting (V+E), tree traversal
• < INT_MAX: O(sqrt(n)), prime, square sum
• < INT_MAX: O(logn), binary search
• < INT_MAX: O(1) Math
Mission News Theme by Compete Themes.