Arrays Flashcards
Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
It turns out we can do it in one-pass. While we iterate and inserting elements into the table, we also look back to check if current element’s complement already exists in the table. If it exists, we have found a solution and return immediately.
class Solution {
public int[] twoSum(int[] nums, int target) {
Map map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int compliment = target - nums[i]; // gets the number needed
// check map
if (map.containsKey(compliment)) {
return new int[] {map.get(compliment), i};
}
// it wasn't in there, put it there
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
Best Time to Buy and Sell Stock
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
class Solution {
public int maxProfit(int[] prices) {
int max = 0;
int j = 1;
for (int i = 0; j < prices.length ; j++) {
if (prices[j] - prices[i] > max) {
max = prices[j] - prices[i];
}
if (prices[i] > prices[j]) {
i = j;
}
}
return max;
}
}Contains Duplicate
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Use a Hash set to store the duplicates, check each time
class Solution {
public boolean containsDuplicate(int[] nums) {
Set set = new HashSet<>();
for (int i = 0; i < nums.length; ++i) {
if (set.contains(nums[i])) {
return true;
}
//isn't twice so add to set
set.add(nums[i]);
}
return false;
}
}
Product of Array Except Self
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Given numbers [2, 3, 4, 5], regarding the third number 4, the product of array except 4 is 235 which consists of two parts: left 23 and right 5. The product is leftright. We can get lefts and rights:
Numbers: 2 3 4 5
Lefts: 2 23 234
Rights: 345 45 5
Let’s fill the empty with 1:
Numbers: 2 3 4 5
Lefts: 1 2 23 234
Rights: 345 45 5 1
We can calculate lefts and rights in 2 loops. The time complexity is O(n).
We store lefts in result array. If we allocate a new array for rights. The space complexity is O(n). To make it O(1), we just need to store it in a variable which is right in @lycjava3’s code.
Clear code with comments:
class Solution {
public int[] productExceptSelf(int[] nums) {
// treat them as values left and right then multiply them together
int n = nums.length;
int[] res = new int[n];
// calculate lefts + store in res
int left = 1;
for (int i = 0; i < n; ++i) {
if (i > 0) {
left = left * nums[i-1];
}
res[i] = left;
}
// calculate rights and the product in res (lefts)
int right = 1;
for (int i = n - 1; i >= 0; i--) {
if (i < n - 1) {
right = right * nums[i + 1];
}
res[i] *= right;
}
return res;
}
}
Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Kadanes Algorithm
class Solution {
public int maxSubArray(int[] nums) {
// Initialize our variables using the first element.
int currentSubarray = nums[0];
int maxSubarray = nums[0];
// Start with the 2nd element since we already used the first one.
for (int i = 1; i < nums.length; i++) {
int num = nums[i];
// If current_subarray is negative, throw it away. Otherwise, keep adding to it.
currentSubarray = Math.max(num, currentSubarray + num);
maxSubarray = Math.max(maxSubarray, currentSubarray);
}
return maxSubarray; } }
Max Subarray Product
Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
It is guaranteed that the answer will fit in a 32-bit integer.
A subarray is a contiguous subsequence of the array.
class Solution {
public int maxProduct(int[] nums) {
if (nums.length == 0) {
return 0;
}
int maxherepre = nums[0]; // pre-calc'd max
int minherepre = nums[0]; // pre-calc'd min
int maxsofar = nums[0]; // global max
int maxhere, minhere; // local min and max
for (int i = 1; i < nums.length; i++) {
maxhere = Math.max(Math.max(maxherepre * nums[i], minherepre * nums[i]), nums[i]); // local max -> previous max and min * nums[i] vs nums[i], can be min b/c negative * negative can make larger
minhere = Math.min(Math.min(maxherepre * nums[i], minherepre * nums[i]), nums[i]); // local min -> previous max and min * nums[i] vs nums[i]
maxsofar = Math.max(maxhere, maxsofar); // current global max
maxherepre = maxhere; // previous max
minherepre = minhere; // previous min (can become max quickly w/ another negative)
}
return maxsofar;
} }
Find Min of rotated array
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
Obvious is to just crawl the array or stream it, but you can use binary search to find the inflection point (not normal binary search) when you do that you get the smallest number!
public int findMin(int[] nums) {
// easiest here is to just crawl array
//return Arrays.stream(nums).min().getAsInt();
// Optimal Solution
if (nums.length == 1) {
return nums[0];
}
// initializing left and right pointers.
int left = 0;
int right = nums.length - 1;
// if the last element is greater than the first element then there is no rotation.
// e.g. 1 < 2 < 3 < 4 < 5 < 7. Already sorted array.
// Hence the smallest element is first element. A[0]
if (nums[right] > nums[left]) {
return nums[left];
}
// binary search (for midpoint cause its smallest)
while (right >= left) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
return nums[mid + 1]; // number to the right is smaller (inflection) so its smallest
}
if (nums[mid - 1] > nums[mid]) {
return nums[mid]; // number before mid is larger so mid must be smallest
}
if (nums[mid] > nums[0]) { // mid is larger than the first element, so the inflection is somewhere to right in array
left = mid + 1;
} else { // mid is greater than zero so we need to move right to the left since we are dealing with smaller #s
right = mid - 1;
}
}
return -1; // its not here
}
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
/*.*/
int left = 0, right = nums.length - 1;
//when we use the condition "left <= right", we do not need to determine if nums[left] == target
//in outside of loop, because the jumping condition is left > right, we will have the determination
//condition if(target == nums[mid]) inside of loop
while (left <= right) {
//left bias
int mid = left + (right - left) / 2;
if (target == nums[mid]) {
return mid;
}
//if left part is monotonically increasing, or the pivot point is on the right part
if (nums[left] <= nums[mid]) {
//must use "<=" at here since we need to make sure target is in the left part,
//then safely drop the right part
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
}
else {
//right bias
left = mid + 1;
}
}
//if right part is monotonically increasing, or the pivot point is on the left part
else {
//must use "<=" at here since we need to make sure target is in the right part,
//then safely drop the left part
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
}
return -1;
}
Three Sum:
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
public List> threeSum(int[] nums) {
Arrays.sort(nums);
List> output = new LinkedList();
for (int i = 0; i < nums.length - 2; ++i) {
if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
int low = i + 1;
int high = nums.length - 1;
int sum = 0 - nums[i];
while (low < high) {
if (nums[low] + nums[high] == sum) {
output.add(Arrays.asList(nums[i], nums[low], nums[high]));
while (low < high && nums[low] == nums[low+1]) low++;
while (low < high && nums[high] == nums[high-1]) high--;
low++;
high--;
} else if (nums[low] + nums[high] > sum) {
high--;
} else {
low++;
}
}
}
}
return output; }
Container With Most Water
Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
public int maxArea(int[] height) {
// start on both sides, calc area, move smaller pointer
// eventually they cross and we have correct value
int max = Integer.MIN_VALUE;
int i = 0;
int j = height.length - 1;
while(i < j) {
int min = Math.min(height[i], height[j]);
max = Math.max(max, min * (j - i));
if (height[i] < height[j]) i++;
else j--;
}
return max;
}
