Missing Number (opens in a new tab)
- The total of the first n natural numbers is
n * (n + 1) / 2 - The difference between the sum of the input array and the total should be the missing number
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function (nums) {
const n = nums.length;
var total = (n * (n + 1)) / 2;
var sum = 0;
for (var i = 0; i < n; i++) {
sum = sum + nums[i];
}
return total - sum;
};Complexity
- Time: O(n)
- Space: O(1)
Concatenation of Array (opens in a new tab)
- Create a new array to hold the concatenated array
- Loop through the input array and push each element to the new array twice
/**
* @param {number[]} nums
* @return {number[]}
*/
var getConcatenation = function (nums) {
const concatNums = [];
for (let i = 0; i < nums.length; i++) {
concatNums.push(nums[i]);
}
for (let i = 0; i < nums.length; i++) {
concatNums.push(nums[i]);
}
return concatNums;
};Complexity
- Time: O(n)
- Space: O(n)
Single Number (opens in a new tab)
- Perform bitwise XOR on all elements in the array
- The XOR operation will cancel out all duplicate numbers, leaving the single number
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function (nums) {
return nums.reduce((x, y) => x ^ y);
};Complexity
- Time: O(n)
- Space: O(1)
Kids With the Greatest Number of Candies (opens in a new tab)
- Find the kid with the most candies & check if each kid can have the most candies by adding extra candies
- Max can also be easily found using
Math.max(...candies)
/**
* @param {number[]} candies
* @param {number} extraCandies
* @return {boolean[]}
*/
var kidsWithCandies = function (candies, extraCandies) {
// find the kid with the most candies
let max = 0;
for (let i = 0; i < candies.length; i++) {
if (max < candies[i]) {
max = candies[i];
}
}
// check if each kid can have the most candies
for (let i = 0; i < candies.length; i++) {
candies[i] = candies[i] + extraCandies >= max;
}
return candies;
};Complexity
- Time: O(n)
- Space: O(n)
Count Tested Devices After Test Operations (opens in a new tab)
- Keep track of the number of devices that have been tested
- Increment the count if the battery percentage is greater than the current count
/**
* @param {number[]} batteryPercentages
* @return {number}
*/
var countTestedDevices = function (batteryPercentages) {
let count = 0;
for (let i = 0; i < batteryPercentages.length; i++) {
if (batteryPercentages[i] > count) {
count++;
}
}
return count;
};Complexity
- Time: O(n)
- Space: O(1)
How Many Numbers Are Smaller Than the Current Number (opens in a new tab)
- Build a count array to store the frequency of each number
- Calculate the number of elements lesser than the current number
/**
* @param {number[]} nums
* @return {number[]}
*/
var smallerNumbersThanCurrent = function (nums) {
const length = nums.length;
const limit = 100;
let countArray = new Array(limit + 1).fill(0);
// build the count array
for (let i = 0; i < length; i++) {
countArray[nums[i]]++;
}
// calculate the number of elements lesser than the current number in one pass
let prevCount = 0;
for (let i = 0; i <= limit; i++) {
if (countArray[i]) {
const currentCount = countArray[i];
countArray[i] = prevCount;
prevCount += currentCount;
}
}
const smallerArray = [];
for (let i = 0; i < length; i++) {
smallerArray.push(countArray[nums[i]]);
}
return smallerArray;
};Complexity
- Time: O(n)
- Space: O(n)
Running Sum of 1d Array (opens in a new tab)
- Naive approach would be to calculate the sum of all the array elements before the current index for every element, in to a new array.
- Simpler and better approach would be to replace the current element by its sum with the previous element
/**
* @param {number[]} nums
* @return {number[]}
*/
var runningSum = function (nums) {
for (let i = 1; i < nums.length; i++) {
nums[i] += nums[i - 1];
}
return nums;
};Complexity
- Time: O(n)
- Space: O(1)
Shuffle the Array (opens in a new tab)
- Simple solution would be to create a new array and shift the elements in the order given
/**
* @param {number[]} nums
* @param {number} n
* @return {number[]}
*/
var shuffle = function (nums, n) {
const newNums = [];
for (let i = 0, j = n; i < n; i++, j++) {
newNums.push(nums[i], nums[j]);
}
return newNums;
};Complexity
- Time: O(n)
- Space: O(n)
Check if Array Is Sorted and Rotated (opens in a new tab)
- In a sorted array, if current value is greater than the next value, then it is unsorted pair
- In a rotated sorted array, there will be only at max one unsorted pair
/**
* @param {number[]} nums
* @return {boolean}
*/
var check = function (nums) {
let unsortedCount = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] > nums[(i + 1) % nums.length]) {
unsortedCount++;
}
if (unsortedCount > 1) {
return false;
}
}
return true;
};Complexity
- Time: O(n)
- Space: O(1)
Matrix Diagonal Sum (opens in a new tab)
- The diagonal sum of matrix can be calculated by calculating the sum of the each diagonal and adding up
- In case the matrix is having odd number of rows, then central element has to be considered only once
/**
* @param {number[][]} mat
* @return {number}
*/
var diagonalSum = function (mat) {
const n = mat.length;
let diagonalSum = 0;
// sum of diagonal from [0, 0] to [n-1, n-1]
for (let i = 0; i < n; i++) {
diagonalSum += mat[i][i];
}
// sum of diagonal from [0, n-1] to [n-1, 0]
for (let i = 0, j = n - 1; i < n; i++, j--) {
diagonalSum += mat[i][j];
}
// if n is odd, then subtract the central element
if (n % 2 === 1) {
diagonalSum -= mat[Math.floor(n / 2)][Math.floor(n / 2)];
}
return diagonalSum;
};Complexity
- Time: O(n)
- Space: O(1)
Check if Number Has Equal Digit Count and Digit Value (opens in a new tab)
- Store the count of each digit in the array
- Compare the count of each digit with the digit value
function digitCount(num) {
const numCount = new Array(10).fill(0);
for (const digit of num) {
numCount[digit]++;
}
for (let idx = 0; idx < num.length; idx++) {
// if count of digit is not equal to digit value
if (numCount[idx] != num[idx]) {
return false;
}
}
return true;
}Complexity
- Time: O(n)
- Space: O(1)
Sum of Unique Elements (opens in a new tab)
- This is basically calculating the frequency of each element and sum up the unique elements (having frequency 1)
/**
* @param {number[]} nums
* @return {number}
*/
var sumOfUnique = function (nums) {
let arr = [],
sum = 0;
for (let i = 0; i < nums.length; i++) {
arr[nums[i]] = (arr[nums[i]] || 0) + 1;
}
for (let i = 0; i < arr.length; i++) {
if (arr[i] == 1) {
sum += i;
}
}
return sum;
};Complexity
- Time: O(n)
- Space: O(n)
Max Consecutive Ones (opens in a new tab)
- Use a counter to keep track of the number of consecutive ones
- Update the maximum count when a zero is encountered
/**
* @param {number[]} nums
* @return {number}
*/
var findMaxConsecutiveOnes = function (nums) {
let count = 0, max = 0;
for (const num of nums) {
if (num) {
count++;
} else {
max = Math.max(max, count);
count = 0;
}
}
return Math.max(max, count); // Edge case when the array ends with 1
};Complexity
- Time: O(n)
- Space: O(1)
Move Zeroes (opens in a new tab)
- Move all non-zero elements to the front of the array
- Fill the remaining elements with zeros
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function (nums) {
let pointer = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i]) {
nums[pointer] = nums[i];
pointer++;
}
}
for (let i = pointer; i < nums.length; i++) {
nums[i] = 0;
}
return nums;
};Complexity
- Time: O(n)
- Space: O(1)
Rotate Array (opens in a new tab)
- Reverse the entire array to get the correct order of the elements
- Reverse the first
kelements and the remaining elements separately
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function (nums, k) {
k = k % nums.length;
nums.reverse();
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
return nums;
};
function reverse(nums, start, end) {
while (start < end) {
// Swap the start and end elements
const temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}Complexity
- Time: O(n)
- Space: O(1)