leetcode Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
[1,1,1,2,2,3]and k = 2, return
- You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
- Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
leetcode Reverse String
Write a function that takes a string as input and returns the string reversed.
Given s = “hello”, return “olleh”.
leetcode Integer Break
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).
Note: you may assume that n is not less than 2.
leetcode Power of Four
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
Given num = 16, return true. Given num = 5, return false.
Follow up: Could you solve it without loops/recursion?
leetcode Counting Bits
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.
num = 5you should return
- It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
- Space complexity should be O(n).
- Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
leetcode House Robber III
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
12345 3/ \2 3\ \3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
12345 3/ \4 5/ \ \1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.
leetcode Self Crossing
You are given an array x of
npositive numbers. You start at point
xmetres to the north, then
xmetres to the west,
xmetres to the south,
xmetres to the east and so on. In other words, after each move your direction changes counter-clockwise.
Write a one-pass algorithm with
O(1)extra space to determine, if your path crosses itself, or not.
Given x =
[2, 1, 1, 2]
Given x =
[1, 2, 3, 4]
false(not self crossing)
Given x =
[1, 1, 1, 1]
leetcode Increasing Triplet Subsequence
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
Formally the function should:
Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.Your algorithm should run in O(n) time complexity and O(1) space complexity.
[1, 2, 3, 4, 5],
[5, 4, 3, 2, 1],
leetcode Patching Array
Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range
[1, n]inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.
[1, 3], n =
Combinations of nums are
, , [1,3], which form possible sums of:
1, 3, 4.
Now if we add/patch
2to nums, the combinations are:
, , , [1,3], [2,3], [1,2,3].
Possible sums are
1, 2, 3, 4, 5, 6, which now covers the range
So we only need
leetcode Odd Even Linked List
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on …