Posts tagged as “O(n)”

花花酱 LeetCode 1306. Jump Game III

By zxi on December 29, 2019

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++

// Author: Huahua

class Solution {

public:

bool canReach(vector<int>& arr, int start) {

const int n = arr.size();

vector<int> seen(n);

seen[start] = 1;

queue<int> q;

q.push(start);

while (q.size()) {

int cur = q.front();

q.pop();

if (arr[cur] == 0) return true;

for (int i : {-1, 1}) {

int t = cur + i * arr[cur];

if (t < 0 || t >= n || seen[t]) continue;

q.push(t);

seen[t] = 1;

}

return false;

}

};

花花酱 LeetCode 1305. All Elements in Two Binary Search Trees

By zxi on December 29, 2019

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++

// Author: Huahua

class Solution {

public:

vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {

function<void(TreeNode*, vector<int>&)> inorder = [&](TreeNode* root, vector<int>& t) {

if (!root) return;

inorder(root->left, t);

t.push_back(root->val);

inorder(root->right, t);

};

vector<int> t1;

vector<int> t2;

inorder(root1, t1);

inorder(root2, t2);

vector<int> m;

int i = 0;

int j = 0;

while (m.size() != t1.size() + t2.size()) {

if (j == t2.size()) m.push_back(t1[i++]);

else if (i == t1.size()) m.push_back(t2[j++]);

else m.push_back(t1[i] < t2[j] ? t1[i++] : t2[j++]);

}

return m;

}

};

C++/STL

// Author: Huahua

class Solution {

public:

vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {

function<void(TreeNode*, vector<int>&)> inorder = [&](TreeNode* root, vector<int>& t) {

if (!root) return;

inorder(root->left, t);

t.push_back(root->val);

inorder(root->right, t);

};

vector<int> t1;

vector<int> t2;

inorder(root1, t1);

inorder(root2, t2);

vector<int> m;

std::merge(begin(t1), end(t1), begin(t2), end(t2), back_inserter(m));

return m;

}

};

花花酱 LeetCode 1304. Find N Unique Integers Sum up to Zero

By zxi on December 29, 2019

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: [0]

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++

// Author: Huahua

class Solution {

public:

vector<int> sumZero(int n) {

vector<int> ans;

for (int i = 1; i <= n / 2; ++i) {

ans.push_back(i);

ans.push_back(-i);

}

if (ans.size() != n) ans.push_back(0);

return ans;

}

};

花花酱 LeetCode 1299. Replace Elements with Greatest Element on Right Side

By zxi on December 28, 2019

Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.

After doing so, return the array.

Example 1:

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]

Constraints:

1 <= arr.length <= 10^4
1 <= arr[i] <= 10^5

Solution: Scan from right to left

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

C++

// Author: Huahua

class Solution {

public:

vector<int> replaceElements(vector<int>& arr) {

int g = -1;

for (int i = arr.size() - 1; i >= 0; --i)

g = max(g, exchange(arr[i], g));

return arr;

}

};

花花酱 LeetCode 1296. Divide Array in Sets of K Consecutive Numbers

By zxi on December 26, 2019

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into sets of k consecutive numbers
Return True if its possibleotherwise return False.

Example 1:

Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].

Example 2:

Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
Output: true
Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].

Example 3:

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

Example 4:

Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= nums.length

Solution: BST + Greedy

Start from the smallest available number and find k consecutive numbers.

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

C++

// Author: Huahua

class Solution {

public:

bool isPossibleDivide(vector<int>& nums, int k) {

if (nums.size() % k) return false;

map<int, int> m;

for (int num : nums) ++m[num];

while (m.size()) {

const int s = m.cbegin()->first;

for (int i = 0; i < k; ++i) {

auto it = m.find(s + i);

if (it == m.cend()) return false;

if (--it->second == 0) m.erase(it);

}

return true;

}

};

C++/V2

// Author: Huahua

class Solution {

public:

bool isPossibleDivide(vector<int>& nums, int k) {

if (nums.size() % k) return false;

map<int, int> m;

for (int num : nums) ++m[num];

while (m.size()) {

auto it = m.begin();

const int s = it->first;

for (int i = 0; i < k; ++i, ++it) {

if (it->first != s + i) return false;

if (--it->second == 0) m.erase(it);

}

return true;

}

};

Solution 2: HashTable

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

C++

class Solution {

public:

bool isPossibleDivide(vector<int>& nums, int k) {

if (nums.size() % k) return false;

unordered_map<int, int> m;

for (int num : nums) ++m[num];

queue<int> starts;

for (auto [n, f] : m)

if (!m.count(n - 1)) starts.push(n);

while (!starts.empty()) {

int s = starts.front();

starts.pop();

for (int t = s + k - 1; t >= s; t--) {

if (m[t] < m[s]) return false;

if ((m[t] -= m[s]) == 0) {

m.erase(t);

if (m.count(t + 1)) starts.push(t + 1);

}

return true;

}

};

Posts tagged as “O(n)”

花花酱 LeetCode 1306. Jump Game III

Solution: BFS / DFS

C++

花花酱 LeetCode 1305. All Elements in Two Binary Search Trees

Solution: Inorder traversal + Merge Sort

C++

C++/STL

花花酱 LeetCode 1304. Find N Unique Integers Sum up to Zero

Solution: Generation

C++

花花酱 LeetCode 1299. Replace Elements with Greatest Element on Right Side

Solution: Scan from right to left

C++

花花酱 LeetCode 1296. Divide Array in Sets of K Consecutive Numbers

Solution: BST + Greedy

C++

C++/V2

Solution 2: HashTable

C++

Related Problems