My LeetCode Diary - Day2 Arrays
977. Squares of a Sorted Array
Example 1:
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
Example 2:
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
Both side after square the number, it both could be the largest number in the new array.
Thus, we use two pointers to index both side of the input arrays.
Next, we compare the result, if the left result is greater than right result, the left pointer move forward one step, vice versa, until left pointer equals to right pointer’s index.
Solution:
class Solution {
public int[] sortedSquares(int[] nums) {
int[] result = new int[nums.length];
int k = nums.length - 1;
// left pointer
int i = 0;
// right pointer
int j = nums.length - 1;
while(i<=j){
if (nums[i]*nums[i] > nums[j] * nums[j]){
result[k--] = nums[i]*nums[i];
i++;
} else {
result[k--] = nums[j] * nums[j];
j--;
}
}
return result;
}
}
Sliding window
A computational technique that aims to reduce the use of nested loops and replace it with a single loop, thereby reducing the time complexity.
209. Minimum Size Subarray Sum
More questions related: No. 904, No. 76
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int res = Integer.MAX_VALUE;
int sum = 0;
for (int right = 0; right <= nums.length - 1; right++){//Sliding the window
sum += nums[right];
while (sum >= target) {
res = Math.min(res, right - left + 1);
sum -= nums[left];
left++; //Reduce the window
}
}
return res == Integer.MAX_VALUE ? 0 : res;
}
}
59. Spiral Matrix II
class Solution {
public int[][] generateMatrix(int n) {
int loop = 0;
int start = 0;
int count = 1;
int[][] res = new int[n][n];
int i,j;
while (loop++ < n/2) {
for (j = start; j < n - loop; j++){
res[start][j] = count++;
}
for (i = start; i < n - loop; i++){
res[i][j] = count++;
}
for (; j >= loop; j--){
res[i][j] = count++;
}
for(; i >= loop; i--) {
res[i][j] = count++;
}
start++;
}
if(n%2 == 1){
res[start][start] = count;
}
return res;
}
}