Leetcode Array Problmes Flashcards
Arrays
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> complement_match;
vector<int> result;
int length = nums.size();
for (int i = 0; i < length; i++) {
int complement = target - nums[i];
if (complement_match.find(complement) != complement_match.end() {
int key_index = complement_match(complement)->second;
result.insert(result.end(), { i, key_index });
}
complement_match.insert({ nums[i], i});
}
return result;
}
};</int></int></int>
For TwoSum there are two ways to solve this problem. Either by brute force, or implementing a hash map.
Brute force allows you to iterate through each item looking for a pair that equals a target. For example nums[i] + nums[j] == target. The problem with this approach is that it is slow. Because you have to scan through the list for each element, making the runtime O(n^2).
The hash map is a better approach because you can take that condition from above nums[i] + nums[j] == target, and and subject nums[j] to the other side. Example nums[i] == target - nums[j]. Now you can take the complement of that equation and insert it into a hash table. Now we have that memory stored and saved we can check for a matching pair based on that complement. If the complement is in the hash map, then we know that there is a match. Now we can iterate through the list with one single scan making the runtime O(n).
- Best Time to Buy and Sell Stock
Solved
Easy
Topics
Companies
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
1 <= prices.length <= 105
0 <= prices[i] <= 104
class Solution {
public:
int maxProfit(vector<int>& prices) {
int min_price = INT_MAX;
int max_profit = 0;
for (const auto& price : prices) {
min_price = min(min_price, price);
int curr_profit = price - min_price;
max_profit = max(max_profit, curr_profit);
}</int>
return max_profit; } };
This is a min-max algorithm. Minimum because we need the lowest price to determined the largest profit we can get in the list. Since we cannot trade on the first day we ignored the first element. Maximum because we return the largest profit. I am iterating the list to find the smallest element in the last, and updating the largest profit in the list.
- Contains Duplicate
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Explanation:
The element 1 occurs at the indices 0 and 3.
Example 2:
Input: nums = [1,2,3,4]
Output: false
Explanation:
All elements are distinct.
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Constraints:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> unique_set;
bool is_duplicate = false;
for (const auto& num : nums) {
if (unique_set.find(num) != unique_set.end()) {
is_duplicate = true;
return is_duplicate;
}
}</int></int>
return is_duplicate; } };
Implement a set. The reasoning for a set is because a set cannot contain any duplicates. Therefore, continue to store element in the set, and if that current element is in the set, then we know that we have a duplicate.
- Product of Array Except Self
Solved
Medium
Topics
Companies
Hint
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 105
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int length = nums.size();
vector<int> prefix(length);
prefix[0] = 1;
for (int i = 1; i < length; i++) {
prefix[i] = prefix[i - 1] * nums[i - 1];
}
vector<int> suffix(length);
suffix[length - 1] = 1;
for (int i = length - 2; i >= 0; i--) {
suffix[i] = suffix[i + 1] * nums[i + 1];
}
vector<int> answer(length);
for (int i = 0; i < length; i++) {
answer[i] = prefix[i] * suffix[i];
}</int></int></int></int></int>
return answer; } };
- Maximum Subarray
Solved
Medium
Topics
Companies
Given an integer array nums, find the
subarray
with the largest sum, and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max_subarray = INT_MIN;
int current_sum = 0;
for (const auto& num : nums) {
current_sum += num;
max_subarray = max(max_subarray, current_sum);
current_sum = current_sum < 0 ? 0 : current_sum;
}</int>
return max_subarray; } };
- Maximum Product Subarray
Solved
Medium
Topics
Companies
Given an integer array nums, find a
subarray
that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints:
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
The product of any subarray of nums is guaranteed to fit in a 32-bit integer.
class Solution {
public:
int maxProduct(vector<int>& nums) {
int max_product = nums[0];
int min_product = nums[0];
int result = nums[0];
int length = nums.size();
for (int i = 1; i < length; i++) {
int current_max = max_product;
max_product = max({ nums[i], nums[i] * max_product, nums[i] * min_product });
min_product = min({ nums[i], nums[i] * current_max, nums[i] * min_product });
result = max(result ,max_product);
}</int>
return result; } };
- Find Minimum in Rotated Sorted Array
Solved
Medium
Topics
Companies
Hint
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
Constraints:
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int middle = left + (right - left) / 2;
if (nums[middle] > nums[right]) {
left = middle + 1;
} else {
right = middle;
}
}</int>
return nums[left]; } };
Use two pointers and check the element in the middle. If the element in the middle is greater than the right side, then we know that the lowest number is on the right. Move left pointer middle + 1 position. If the opposite occurs move right pointer to the middle position. Keep looping until left < right became invalid.
- Search in Rotated Sorted Array
Solved
Medium
Topics
Companies
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:
Input: nums = [1], target = 0
Output: -1
Constraints:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-104 <= target <= 104
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int middle = left + (right - left) / 2;
if (nums[middle] == target) {
return middle;
}
if (nums[left] <= nums[middle]) {
if (target > nums[middle] || target < nums[left]) {
left = middle + 1;
} else {
right = middle - 1;
}
} else {
if (target < nums[middle] || target > nums[right]) {
right = middle - 1;
} else {
left = middle + 1;
}
}
}</int>
return -1; } };
Dividing the problem into two sides left and right. If the target is greater than the element in the middle than we know that the target number is on the right hand side otherwise it is on the left hand side. Furthermore, if the target number is less than the number on the left hand side we know that the target is on the right side.
- 3Sum
Solved
Medium
Topics
Companies
Hint
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
int length = nums.size();
for (int current_index = 0; current_index < length; current_index++) {
int previous_index = current_index - 1;
if (current_index == 0 || nums[current_index] != nums[previous_index]) {
int left = current_index + 1;
int right = length - 1;
while (left < right) {
int target = -1 * (nums[current_index]);
int sum = nums[left] + nums[right];
if (target == sum) {
result.push_back({ nums[current_index], nums[left], nums[right] });
while (left < right && nums[left] == nums[left + 1]) {
\++left;
}
while (left < right && nums[right] == nums[right - 1]) {
--right;
}
\++left;
--right;
} else if (target > sum) {
\++left;
} else {
--right;
}
}
}
}</int></int></int>
return result; } };
- Container With Most Water
Solved
Medium
Topics
Companies
Hint
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1]
Output: 1
Constraints:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int max_area = INT_MIN;
while (left < right) {
int width = right - left;
int min_length = min(height[left], height[right]);
int current_area = width * min_length;
max_area = max(max_area, current_area);
height[left] < height[right] ? ++left : --right;
}</int>
return max_area; } };
