# Posts tagged as “O(n)”

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

## Solution 1: Brute Force

r[i] = min(max(h[0:i+1]), max(h[i:n]))
ans = sum(r[i])

Time complexity: O(n^2)
Space complexity: O(1)

## Solution 2: DP

l[i] := max(h[0:i+1])
r[i] := max(h[i:n])
ans = sum(min(l[i], r[i]) – h[i])

Time complexity: O(n)
Space complexity: O(n)

## Solution 3: Two Pointers

Time complexity: O(n)
Space complexity: O(1)

## C++

Given the array arr of positive integers and the array queries where queries[i] = [Li, Ri], for each query i compute the XOR of elements from Li to Ri (that is, arr[Li] xor arr[Li+1] xor ... xor arr[Ri] ). Return an array containing the result for the given queries.

Example 1:

Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8]
Explanation:
The binary representation of the elements in the array are:
1 = 0001
3 = 0011
4 = 0100
8 = 1000
The XOR values for queries are:
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[3,3] = 8


Example 2:

Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
Output: [8,0,4,4]


Constraints:

• 1 <= arr.length <= 3 * 10^4
• 1 <= arr[i] <= 10^9
• 1 <= queries.length <= 3 * 10^4
• queries[i].length == 2
• 0 <= queries[i] <= queries[i] < arr.length

## Solution: Prefix Sum

Time complexity: O(n) + O(q)
Space complexity: O(n)

## C++

tby

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation:
All possible ways to reach at index 3 with value 0 are:
index 5 -> index 4 -> index 1 -> index 3
index 5 -> index 6 -> index 4 -> index 1 -> index 3


Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true
Explanation:
One possible way to reach at index 3 with value 0 is:
index 0 -> index 4 -> index 1 -> index 3


Example 3:

Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.


Constraints:

• 1 <= arr.length <= 5 * 10^4
• 0 <= arr[i] < arr.length
• 0 <= start < arr.length

## Solution: BFS / DFS

Time complexity: O(n)
Space complexity: O(n)

## C++

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]


Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]


Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]


Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]


Example 5:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]


Constraints:

• Each tree has at most 5000 nodes.
• Each node’s value is between [-10^5, 10^5].

## Solution: Inorder traversal + Merge Sort

Time complexity: O(t1 + t2)
Space complexity: O(t1 + t2)

## C++/STL

Given an integer n, return any array containing n unique integers such that they add up to 0.

Example 1:

Input: n = 5
Output: [-7,-1,1,3,4]
Explanation: These arrays also are accepted [-5,-1,1,2,3] , [-3,-1,2,-2,4].


Example 2:

Input: n = 3
Output: [-1,0,1]


Example 3:

Input: n = 1
Output: 


Constraints:

• 1 <= n <= 1000

## Solution: Generation

Use numbers from {-n/2, … n/2} + {0 if n is odd}

Time complexity: O(n)
Space complexity: O(1)

## C++

Mission News Theme by Compete Themes.