A summary of array related problems from LeetCode with solutions in C++.
Problems:
704. Binary Search
27. Remove Element
977. Squares of a Sorted Array
209. Minimum Size Subarray Sum
59. Spiral Matrix II
Problem: Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity.
Case 1: Input: nums = [-1,0,3,5,9,12], target = 9, Output: 4
Case 2: Input: nums = [-1,0,3,5,9,12], target = 2, Output: -1
// C++
class Solution1 {
public:
int search(vector<int>& nums, int target) {
int leftIdx = 0;
int rightIdx = nums.size()-1;
// Assume [leftIdx, rightIdx]
while (leftIdx <= rightIdx) {
int middleIdx = leftIdx + ((rightIdx-leftIdx)/2);
if (nums[middleIdx] > target) {
rightIdx = middleIdx - 1; // [leftIdx, middleIdx-1]
} else if (nums[middleIdx] < target) {
leftIdx = middleIdx + 1; // [middleIdx+1, rightIdx]
} else { // nums[middleIdx] == target
return middleIdx;
}
}
// Target is not in nums
return -1;
}
};
class Solution2 {
public:
int search(vector<int>& nums, int target) {
int leftIdx = 0;
int rightIdx = nums.size()-1;
// Assume [leftIdx, rightIdx)
while (leftIdx < rightIdx) {
int middleIdx = leftIdx + ((rightIdx-leftIdx)/2);
if (nums[middleIdx] > target) {
rightIdx = middleIdx; // [leftIdx, middleIdx)
} else if (nums[middleIdx] < target) {
leftIdx = middleIdx + 1; // [middleIdx+1, rightIdx)
} else { // nums[middleIdx] == target
return middleIdx;
}
}
// Target is not in nums
return -1;
}
};
Related problems
35. Search Insert Position
34. Find First and Last Position of Element in Sorted Array
69. Sqrt(x)
367. Valid Perfect Square
Problem: Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed. Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements. Return k after placing the final result in the first k slots of nums. Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
Case 1: Input: nums = [3,2,2,3], val = 3, Output: 2, nums = [2,2,_,_]
Case 2: Input: nums = [0,1,2,2,3,0,4,2], val = 2, Output: 5, nums = [0,1,4,0,3,_,_,_]
// C++
class SolutionSlow {
public:
// Time complexity: O(n^2)
// Space complexity: O(1)
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
for (int i = 0; i < size; i++) {
// Val found, move all other items' index by 1
if (nums[i] == val) {
for (int j = i + 1; j < size; j++) {
nums[j-1] = nums[j];
}
i--; // move index forward by 1
size--; // shrink size by 1
}
}
return size;
}
};
// C++
class SolutionFast {
public:
// Time complexity: O(n)
// Space complexity: O(1)
int removeElement(vector<int>& nums, int val) {
// slowIdx is used to track valid update positions in the old array
int slowIdx = 0;
// fastIdx is used to search for valid items in the new array,
// namely exclude val
for (int fastIdx = 0; fastIdx < nums.size(); fastIdx++) {
if(val != nums[fastIdx]) {
// nums[slowIdx++] = nums[fastIdx];
nums[slowIdx] = nums[fastIdx];
slowIdx++;
}
}
return slowIdx;
}
};
class SolutionFast {
public:
// Time complexity: O(n)
// Space complexity: O(1)
// This method might change the order of the new array.
// This method uses smallest movements of items
int removeElement(vector<int>& nums, int val) {
int leftIdx = 0;
int rightIdx = nums.size() - 1;
while (leftIdx <= rightIdx) {
// Find leftIdx that nums[leftIdx] == val
while (leftIdx <= rightIdx && nums[leftIdx] != val){
leftIdx++;
}
// Find rightIdx that nums[rightIdx] != val
while (leftIdx <= rightIdx && nums[rightIdx] == val) {
rightIdx--;
}
// Let nums[leftIdx] = nums[rightIdx]
if (leftIdx < rightIdx) {
// nums[leftIdx++] = nums[rightIdx--];
nums[leftIdx] = nums[rightIdx];
leftIdx++;
rightIdx--;
}
}
// leftIdx points to the next item of the valid last item
return leftIdx;
}
};
Related problems
26. Remove Duplicates from Sorted Array
283. Move Zeroes
844. Backspace String Compare
3. 977. Squares of a Sorted Array
Problem: Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Case 1: Input: nums = [-4,-1,0,3,10], Output: [0,1,9,16,100]
Case 2: Input: nums = [-7,-3,2,3,11], Output: [4,9,9,49,121]
// C++
class Solution1 {
public:
// Time complexity: O(n + nlog(n))
vector<int> sortedSquares(vector<int>& nums) {
for (int i = 0; i < nums.size(); i++) {
nums[i] *= nums[i];
}
// Quick sort
sort(nums.begin(), nums.end());
return nums;
}
};
class Solution2 {
public:
// Time complexity: O(n)
vector<int> sortedSquares(vector<int>& nums) {
// Init a result vector
vector<int> result(nums.size(), 0);
int rIdx = nums.size() - 1;
// Double pointers
int i = 0;
int j = nums.size() - 1;
while (i <= j) {
if ((nums[i] * nums[i]) < (nums[j] * nums[j])) {
// result[rIdx--] = nums[j] * nums[j];
result[rIdx] = nums[j] * nums[j];
rIdx--;
j--;
} else {
// result[rIdx--] = nums[i] * nums[i];
result[rIdx] = nums[i] * nums[i];
rIdx--;
i++;
}
}
return result;
}
};
4. 209. Minimum Size Subarray Sum
Problem: Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Case 1: Input: target = 7, nums = [2,3,1,2,4,3], Output: 2
Case 2: Input: target = 4, nums = [1,4,4], Output: 1
Case 3: Input: target = 11, nums = [1,1,1,1,1,1,1,1], Output: 0
// C++
class Solution {
public:
// Time complexity: O(n)
// Space compexity: O(1)
int minSubArrayLen(int target, vector<int>& nums) {
int result = INT32_MAX; // minimal length
int sum = 0; // sum of sliding window
int sIdx = 0; // start index of sliding window
int subLength = 0; // sub length of sliding window
// eIdx: end index of sliding window
for (int eIdx = 0; eIdx < nums.size(); eIdx++) {
// Sum items till sum >= target
sum += nums[eIdx];
while (sum >= target) {
// Get length of sliding window
subLength = eIdx - sIdx + 1;
// Update minimal length
result = result < subLength ? result : subLength;
// Update sum, sum -= nums[sIdx++];
sum -= nums[sIdx];
sIdx++;
}
}
// No update on result, return 0
return result == INT32_MAX ? 0 : result;
}
};
Related problems
904. Fruit Into Baskets
76. Minimum Window Substring
Problem: Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.
Case 1: Input: n = 3, Output: [[1,2,3],[8,9,4],[7,6,5]]
Case 2: Input: n = 1, Output: [[1]]
// C++
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
// Define a 2D array in n x n
vector<vector<int>> resultMatrix(n, vector<int>(n, 0));
// Define loop number
int loop = n/2;
// Define center index of matrix, n = 5, mid = 2, namely (2, 2)
int midIdx = n/2;
// Define loop start index
int startX = 0;
int startY = 0;
// Init offset for each row, column
int offset = 1;
// Init value for each cell of result matrix
int count = 1;
// Init index
int i, j;
while (loop--) {
i = startX; // row
j = startY; // column
// [Top row)
for (j = startY; j < n - offset; j++) {
// resultMatrix[startX][j] = count++;
resultMatrix[startX][j] = count;
count++;
} // j == n - offset
// [Right column)
for (i = startX; i < n - offset; i++) {
// resultMatrix[i][j] = count++;
resultMatrix[i][j] = count;
count++;
} // i == n - offset and j == n - offset
// [Bottom row)
for (; j > startY; j--) {
// resultMatrix[i][j] = count++;
resultMatrix[i][j] = count;
count++;
} // j == startY
// [Left column)
for (; i > startX; i--) {
// resultMatrix[i][j] = count++;
resultMatrix[i][j] = count;
count++;
} // i == startX and j == startY
// Next loop, increase startX, startY by 1
// First loop: (0, 0), second loop: (1, 1)
startX++;
startY++;
// Next loop, increase offset by 1
offset++;
}
// n is an odd number
if (n % 2 == 1) {
resultMatrix[midIdx][midIdx] = count;
}
return resultMatrix;
}
};
Related problems
54. Spiral Matrix