Arrays Flashcards
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
/**
* @param {number[]} nums
*/
var NumArray = function(nums) {
this.nums = nums;
};
/**
* @param {number} i
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function(i, j) {
let sum = 0;
for (let a = i; a <= j; a++) {
sum += this.nums[a];
}
return sum;
};
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function(nums1, m, nums2, n) {
let counter = 0;
for (let i = m; i < nums1.length; i++) {
nums1[i] = nums2[counter];
counter++;
}
nums1 = nums1.sort((a, b) => a - b);
};Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4]
Output: [24,12,8,6]
/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function(nums) {
const output = [];
for (let i = 0; i < nums.length; i++) {
let product = 1;
for (let j = 0; j < nums.length; j++) {
if (i !== j) {
product *= nums[j];
}
}
output[i] = product;
}
return output; };
Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.
Example 1:
Input: [3,0,1]
Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {
for (let i = 0; i < nums.length; i++) {
if (nums.indexOf(i) === -1) {
return i;
}
}
return nums.length;
};Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {
for (let i = 0; i < nums.length; i++) {
if (nums.indexOf(i) === -1) {
return i;
}
}
return nums.length;
};Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.
/**
* @param {string[]} words
* @return {string[]}
*/
var findWords = function(words) {
const alphabet = [['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'],
['a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'],
['z', 'x', 'c', 'v', 'b', 'n', 'm']];
const foundWords = [];
for (let word of words) {
const firstLetter = word[0];
let row = 0;
let isFound = true;
if(!alphabet[0].includes(firstLetter.toLowerCase())) {
if (alphabet[1].includes(firstLetter.toLowerCase())) {
row = 1;
} else {
row = 2;
}
}
for (let i = 1; i < word.length; i++) {
if (!alphabet[row].includes(word[i].toLowerCase())) {
isFound = false;
}
}
if (isFound) {
foundWords.push(word);
}
}
return foundWords; };
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1,2,3,6,9,8,7,4,5]
/**
* @param {number[][]} matrix
* @return {number[]}
*/
var spiralOrder = function(matrix) {
const output = [];
if (matrix.length === 0) {
return output;
}
let r1 = 0;
let r2 = matrix.length - 1;
let c1 = 0;
let c2 = matrix[0].length - 1;
while (r1 <= r2 && c1 <= c2) {
for (let c = c1; c <= c2; c++) {
output.push(matrix[r1][c]);
}
for (let r = r1 + 1; r <= r2; r++) {
output.push(matrix[r][c2]);
}
if (r1 < r2 && c1 < c2) {
for (let c = c2 - 1; c > c1; c--) {
output.push(matrix[r2][c]);
}
for (let r = r2; r > r1; r--) {
output.push(matrix[r][c1]);
}
}
r1++;
r2--;
c1++;
c2--;
}
return output; };
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Given input matrix = [ [1,2,3], [4,5,6], [7,8,9] ],
rotate the input matrix in-place such that it becomes: [ [7,4,1], [8,5,2], [9,6,3] ]
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var rotate = function(matrix) {
let n = matrix.length;
if(!n) {
return;
}
let i = 0;
while(i < n - 1 && i >= 0) {
for(let p = i; p < n - 1 - i; p++){
// we will keep swapping four corner elements
let temp = matrix[n-1-i][p];
matrix[n-1-i][p]=matrix[n-1-p][n-1-i];
matrix[n-1-p][n-1-i]=matrix[i][n-1-p];
matrix[i][n-1-p]=matrix[p][i];
matrix[p][i]=temp;
}
i++;
}
};
Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.
Follow up:
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
Example 1:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function(matrix) {
const rowCount = matrix.length;
const colCount = matrix[0].length;
const realMatrix = [];
for (let row = 0; row < rowCount; row++) {
for (let col = 0; col < colCount; col++) {
if (realMatrix[row]) {
realMatrix[row][col] = matrix[row][col];
} else {
realMatrix[row] = [];
realMatrix[row][col] = matrix[row][col];
}
}
}
for (let row = 0; row < rowCount; row++) {
for (let col = 0; col < colCount; col++) {
if (realMatrix[row][col] === 0) {
for (let i = 0; i < colCount; i++) {
matrix[row][i] = 0;
}
// fill the col with zeros
for (let j = 0; j < rowCount; j++) {
matrix[j][col] = 0;
}
}
}
}
};
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
/*
We default to say the the best maximum seen so far is the first
element.
We also default to say the the best max ending at the first element
is...the first element.
*/
let maxSoFar = nums[0];
let maxEndingHere = nums[0];
/*
We will investigate the rest of the items in the array from index
1 onward.
*/
for (let i = 1; i < nums.length; i++) {
/*
We are inspecting the item at index i.
We want to answer the question:
"What is the Max Contiguous Subarray Sum we can achieve ending at index i?"
We have 2 choices:
maxEndingHere + nums[i] (extend the previous subarray best whatever it was)
1.) Let the item we are sitting at contribute to this best max we achieved
ending at index i - 1.
nums[i] (start and end at this index)
2.) Just take the item we are sitting at's value.
The max of these 2 choices will be the best answer to the Max Contiguous
Subarray Sum we can achieve for subarrays ending at index i.
Example:
index 0 1 2 3 4 5 6 7 8
Input: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
-2, 1, -2, 4, 3, 5, 6, 1, 5 'maxEndingHere' at each point
The best subarrays we would take if we took them:
ending at index 0: [ -2 ] (snippet from index 0 to index 0)
ending at index 1: [ 1 ] (snippet from index 1 to index 1) [we just took the item at index 1]
ending at index 2: [ 1, -3 ] (snippet from index 1 to index 2)
ending at index 3: [ 4 ] (snippet from index 3 to index 3) [we just took the item at index 3]
ending at index 4: [ 4, -1 ] (snippet from index 3 to index 4)
ending at index 5: [ 4, -1, 2 ] (snippet from index 3 to index 5)
ending at index 6: [ 4, -1, 2, 1 ] (snippet from index 3 to index 6)
ending at index 7: [ 4, -1, 2, 1, -5 ] (snippet from index 3 to index 7)
ending at index 8: [ 4, -1, 2, 1, -5, 4 ] (snippet from index 3 to index 8)
Notice how we are changing the end bound by 1 everytime.
*/
maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]);
// Did we beat the 'maxSoFar' with the 'maxEndingHere'?
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar; };
Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.
Example 1:
Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findMaxAverage = function(nums, k) {
let sum = 0;
for (let i = 0 ;i < k; i++) {
sum += nums[i];
}
let res = sum;
for (let i = k; i < nums.length; i++) {
sum += nums[i] - nums[i - k];
res = Math.max(res, sum);
}
return res/k; };
