Loops Flashcards
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
Example 1:
Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.
Example 2:
Input: [1, 2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
/**
* @param {number[]} nums
* @return {number}
*/
var thirdMax = function(nums) {
let firstMax = null;
let secondMax = null;
let thirdMax = null;
for (const num of nums) {
if (firstMax === null || num > firstMax) {
thirdMax = secondMax;
secondMax = firstMax;
firstMax = num;
} else if (num === firstMax) {
continue;
} else if (secondMax === null || num > secondMax) {
thirdMax = secondMax;
secondMax = num;
} else if (num === secondMax) {
continue;
} else if (thirdMax === null || num > thirdMax) {
thirdMax = num;
}
}
if (thirdMax !== null) {
return thirdMax;
}
return firstMax; };
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.
Example 1:
Input: [“h”,”e”,”l”,”l”,”o”]
Output: [“o”,”l”,”l”,”e”,”h”]
/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function(s) {
let startIndex = 0;
let endIndex = s.length - 1;
while (startIndex < endIndex) {
let temp = s[startIndex];
s[startIndex] = s[endIndex];
s[endIndex] = temp;
startIndex++;
endIndex--;
}
};Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note: For the purpose of this problem, we define empty string as valid palindrome.
Example 1:
Input: “A man, a plan, a canal: Panama”
Output: true
Example 2:
Input: “race a car”
Output: false
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
const reg = new RegExp('^[a-z0-9]$');
let sIndex = 0;
let eIndex = s.length - 1;
const alphanumericString = s.match(reg);
while (sIndex < eIndex) {
let letterA = s[sIndex].toLowerCase();
let letterB = s[eIndex].toLowerCase();
if (reg.test(letterA) && reg.test(letterB)) {
if (letterA !== letterB) {
return false;
}
sIndex++;
eIndex--;
} else {
if (!reg.test(letterA)) {
sIndex++;
} else {
eIndex--;
}
}
} return true; };
Given an integer number n, return the difference between the product of its digits and the sum of its digits.
Example 1: Input: n = 234 Output: 15 Explanation: Product of digits = 2 * 3 * 4 = 24 Sum of digits = 2 + 3 + 4 = 9 Result = 24 - 9 = 15
Example 2: Input: n = 4421 Output: 21 Explanation: Product of digits = 4 * 4 * 2 * 1 = 32 Sum of digits = 4 + 4 + 2 + 1 = 11 Result = 32 - 11 = 21
/**
* @param {number} n
* @return {number}
*/
var subtractProductAndSum = function(n) {
let sum = 0;
let product = 1;
while (n > 0) {
const lastDigit = n % 10;
sum += lastDigit;
product *= lastDigit;
n = Math.floor(n / 10);
}
return product - sum; };
Let’s call an array A a mountain if the following properties hold:
A.length >= 3
There exists some 0 < i < A.length - 1 such that A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1]
Given an array that is definitely a mountain, return any i such that A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1].
Example 1:
Input: [0,1,0]
Output: 1
Example 2:
Input: [0,2,1,0]
Output: 1
/**
* @param {number[]} A
* @return {number}
*/
var peakIndexInMountainArray = function(A) {
let i = 0;
while (A[i] < A[i + 1]) {
i++;
};
return i;
};There is a robot starting at position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.
The move sequence is represented by a string, and the character moves[i] represents its ith move. Valid moves are R (right), L (left), U (up), and D (down). If the robot returns to the origin after it finishes all of its moves, return true. Otherwise, return false.
Note: The way that the robot is “facing” is irrelevant. “R” will always make the robot move to the right once, “L” will always make it move left, etc. Also, assume that the magnitude of the robot’s movement is the same for each move.
Example 1:
Input: “UD”
Output: true
Explanation: The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true.
Example 2:
Input: “LL”
Output: false
Explanation: The robot moves left twice. It ends up two “moves” to the left of the origin. We return false because it is not at the origin at the end of its moves.
/**
* @param {string} moves
* @return {boolean}
*/
var judgeCircle = function(moves) {
let x = 0;
let y = 0;
let R = 'R';
let L = 'L';
let U = 'U';
let D = 'D';
for (let i = 0; i < moves.length; i++) {
const step = moves[i];
if (step === R) {
x += 1;
} else if (step === L) {
x -= 1;
} else if (step === U) {
y += 1;
} else if (step === D) {
y -= 1;
}
}
return x === 0 && y === 0;
};Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:
Input: “abc”
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.
Example 2:
Input: “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.
/**
* @param {string} s
* @return {number}
*/
var countSubstrings = function(s) {
let N = s.length;
let ans = 0;
for (let center = 0; center <= 2*N - 1; center++) {
let left = Math.floor(center / 2);
let right = Math.floor(left + center % 2);
while (left >= 0 && right < N && s[left] === s[right]) {
ans++;
left--;
right++;
}
}
return ans;
};Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).
Example 1:
Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3.
Even though [1,3,5,7] is also an increasing subsequence, it’s not a continuous one where 5 and 7 are separated by 4.
Example 2:
Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1.
/**
* @param {number[]} nums
* @return {number}
*/
var findLengthOfLCIS = function(nums) {
if (nums.length === 0) {
return 0;
}
let longestArrays = [];
let longestArr = [nums[0]];
for (let i = 1; i < nums.length; i++) {
const lastIndexInLongestArr = longestArr.length - 1;
if (longestArr[lastIndexInLongestArr] < nums[i]) {
longestArr.push(nums[i]);
} else {
longestArrays.push(longestArr);
longestArr = [nums[i]];
}
}
longestArrays.push(longestArr);
let maxLength = longestArrays[0].length;
for (let i = 1; i < longestArrays.length; i++) {
if (maxLength < longestArrays[i].length) {
maxLength = longestArrays[i].length;
}
}
return maxLength; };
Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
/**
* @param {number} numRows
* @return {number[][]}
*/
var generate = function(numRows) {
const res = [];
for (let row = 0; row < numRows; row++) {
if (row === 0) {
res.push([1]);
} else if (row === 1) {
res.push([1, 1]);
} else {
res[row] = [];
for (let col = 0; col <= row; col++) {
if (col === 0 || col === row) {
res[row].push(1);
} else {
const sumAbove = res[row - 1][col - 1] + res[row - 1][col];
res[row].push(sumAbove);
}
}
}
}
return res; };
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = “hello”, needle = “ll”
Output: 2
Example 2:
Input: haystack = “aaaaa”, needle = “bba”
Output: -1
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
if (!needle) {
return 0;
}
const match = haystack.match(needle);
if (match) {
return match.index;
}
return -1; };
Second solution:
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
if (!needle) {
return 0;
}
if (haystack.includes(needle)) {
for (let i = 0; i < haystack.length; i++) {
if (haystack.substr(i, needle.length) === needle) {
return i;
}
}
}
return -1; };
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [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.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let max_profit = 0;
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
const profit = prices[j] - prices[i];
if (max_profit < profit) {
max_profit = profit;
}
}
}
return max_profit;
};Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.
Example 1:
Input: [“flower”,”flow”,”flight”]
Output: “fl”
Example 2:
Input: [“dog”,”racecar”,”car”]
Output: “”
Explanation: There is no common prefix among the input strings.
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
if (strs.length === 0) {
return "";
}
for (let i = 0; i < strs[0].length; i++) {
let char = strs[0][i];
for (let j = 1; j < strs.length; j++) {
if (i === strs[j].length || strs[j][i] !== char) {
return strs[0].substring(0, i);
}
}
}
return strs[0]; };
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
/**
- @param {number[]} nums
- @return {boolean}
- /
let canJumpFromPosition = function(position, nums) {
if (position === nums.length - 1) {
return true;
}
let furthestJump = Math.min(position + nums[position], nums.length - 1);
for (let nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
if (canJumpFromPosition(nextPosition, nums)) {
return true;
}
}
return false;
}
var canJump = function(nums) {
return canJumpFromPosition(0, nums);
};
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
Formally the function should:
Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.
Example 1:
Input: [1,2,3,4,5]
Output: true
Example 2:
Input: [5,4,3,2,1]
Output: false
/**
* @param {number[]} nums
* @return {boolean}
*/
var increasingTriplet = function(nums) {
let min1 = Number.MAX_VALUE, min2 = Number.MAX_VALUE;
for (const n of nums){
if (n <= min1) min1 = n;
else if (n <= min2) min2 = n;
else return true;
}
return false;
};Find largest element
int[] a = {5, 7, 8, 9, -1, 3};
int maximum = a[0];
for (int i = 1; i < a.length; i++)
if (a[i] > maximum)
maximum = a[i];
