Code Flashcards
Two sum
import java.util.HashMap;
public class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
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.
public class MaxProfit {
public int maxProfit(int[] prices) {
int maxProfit = 0;
int minPrice = Integer.MAX_VALUE;
// Iterate through each price
for (int price : prices) {
// Update the minimum price seen so far
minPrice = Math.min(minPrice, price);
// Calculate the profit if selling at the current price
int profit = price - minPrice;
// Update the maximum profit seen so far
maxProfit = Math.max(maxProfit, profit);
}
return maxProfit;
}
public static void main(String[] args) {
MaxProfit mp = new MaxProfit();
int[] prices = {7, 1, 5, 3, 6, 4}; // Example prices
System.out.println("Maximum profit: " + mp.maxProfit(prices));
} }
Majority Element
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
public class MajorityElement {
public int majorityElement(int[] nums) {
int majorityElement = nums[0];
int count = 1;
// Iterate through the array starting from the second element
for (int i = 1; i < nums.length; i++) {
// If count becomes 0, reset the majority element to the current element
if (count == 0) {
majorityElement = nums[i];
count = 1;
} else if (nums[i] == majorityElement) {
// If the current element is equal to the majority element, increment count
count++;
} else {
// If the current element is not equal to the majority element, decrement count
count--;
}
}
return majorityElement;
}
public static void main(String[] args) {
MajorityElement me = new MajorityElement();
int[] nums1 = {3, 2, 3}; // Example 1
System.out.println("Majority Element: " + me.majorityElement(nums1));
int[] nums2 = {2, 2, 1, 1, 1, 2, 2}; // Example 2
System.out.println("Majority Element: " + me.majorityElement(nums2));
} }
ontainer With Most Water
Problem Statement: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.
Example:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The maximum area of the container is min(8, 7) * 7 = 49.
public class Solution {
public int maxArea(int[] height) {
int maxArea = 0;
int left = 0;
int right = height.length - 1;
while (left < right) {
int currentArea = Math.min(height[left], height[right]) * (right - left);
maxArea = Math.max(maxArea, currentArea);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
} } . Optimal Exploration: With two pointers, left and right, positioned at the beginning and end of the array respectively, the algorithm starts with the widest possible container. It then gradually narrows down the width by moving the pointers towards each other.
2. Maximizing Area: At each step, the algorithm calculates the area between the lines at positions left and right. To maximize the area, it is crucial to prioritize pairs of lines with greater heights. By moving the pointer with the smaller height towards the other pointer, the algorithm ensures that it is always considering the maximum possible height for the current width.
3. Avoiding Redundancy: The two-pointer approach efficiently explores all possible pairs of lines without redundantly examining pairs that are guaranteed to yield smaller areas. It achieves this by always advancing the pointer associated with the smaller height, as moving the pointer associated with the larger height will not increase the area.
Problem Title: Merge Intervals
Problem Statement:Given a collection of intervals, merge all overlapping intervals.
Example:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
This solution merges overlapping intervals by first sorting the intervals based on their start times. Then, it iterates through the sorted intervals, merging overlapping intervals as it encounters them. Finally, it returns the merged intervals as a 2D array.
Java Solution:
import java.util.*;
public class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length <= 1) {
return intervals;
}
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
int[] currentInterval = intervals[0];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= currentInterval[1]) {
currentInterval[1] = Math.max(currentInterval[1], intervals[i][1]);
} else {
merged.add(currentInterval);
currentInterval = intervals[i];
}
}
merged.add(currentInterval);
return merged.toArray(new int[merged.size()][]);
} }
Longest Substring Without Repeating Characters
Problem Statement:Given a string s, find the length of the longest substring without repeating characters.
Example:
Input: s = “abcabcbb”
Output: 3
Explanation: The longest substring without repeating characters is “abc”, which has a length of 3.
import java.util.*;
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int maxLength = 0;
Map<Character, Integer> charIndexMap = new HashMap<>();
int left = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
if (charIndexMap.containsKey(ch)) {
left = Math.max(left, charIndexMap.get(ch) + 1);
}
charIndexMap.put(ch, right);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
} }
Problem Title: Coin Change
Problem Statement:You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. You need to find the minimum number of coins needed to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount]; }
“Longest Increasing Subsequence” problem.
Problem Title: Longest Increasing Subsequence
Problem Statement:
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example:
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int maxLength = 1;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength; } If nums[j] < nums[i], it means nums[i] can extend the subsequence that ends at nums[j].
* Update dp[i]:
Longest Consecutive Sequence (
Problem Statement:
Given an unsorted array of integers, find the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time complexity.
Example:
Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
import java.util.HashSet;
public class Solution {
public int longestConsecutive(int[] nums) {
HashSet<Integer> numSet = new HashSet<>();
for (int num : nums) {
numSet.add(num);
}</Integer>
int longestStreak = 0;
for (int num : nums) {
if (!numSet.contains(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (numSet.contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
} }
HashSet for Constant Time Lookups:
* A HashSet is used to store all the elements of the input array. The key property of a HashSet is that it provides O(1) average time complexity for lookups, which is crucial for efficiently checking the presence of elements.
2. Greedy Approach:
* The algorithm uses a greedy approach by attempting to build and count the length of sequences starting from the smallest possible element of each sequence.
3. Linear Time Complexity:
* The problem requires a solution with O(n) time complexity. By using a HashSet to handle lookups and by only iterating through the array a couple of times (once to populate the HashSet and once to find sequences), the solution meets this requirement.
4. Avoiding Duplicate Work:
* The condition if (!numSet.contains(num - 1)) ensures that we only start counting a sequence from its smallest element, which avoids redundant work and ensures that each sequence is counted only once.
