Array

Question 1

Two Sum
* Problem: Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.
* Example: Input: [2, 7, 11, 15], target = 9; Output: [0, 1]

Answer 1

Solution: Use a HashMap to store the complement of each number as you iterate through the array. If the complement is found, return its index along with the current index.

2. Create a HashMap to store the values from the array and their corresponding indices.
3. Iterate through the array, and for each element, calculate its complement by subtracting it from the target.
   we calculate the complement, which is the value we need to add to the current element to reach the target value.
   For example, if the target is 9 and the current element is 7, the complement is 2.
4. Check if the complement is already in the HashMap. If it is, that means we’ve found two elements that add up to the target - return the indices of the complement and the current element.
5. If the complement is not in the HashMap, store the current element and its index in the HashMap for future reference.
   If no solution is found, you can choose to throw an exception or return an empty array to indicate that there are no two elements that add up to the target.

Question 2

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.

Example 1:
Input: prices = [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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Answer 2

By initializing minPrice to Integer.MAX_VALUE, we ensure that
The first price will always be less than Integer.MAX_VALUE.
Thus, minPrice is correctly set to the first price in the array.
vs initializing as an arbitary value liek 0 that could actually mess up calcs

1. Track Minimum Price: We need to keep track of the minimum price encountered so far as we iterate through the prices.
2. Calculate Profit: For each price, calculate the profit if we were to sell on that day (current price minus the minimum price seen so far).
3. Track Maximum Profit: Keep track of the maximum profit encountered during these calculations.

When the min_price updates, it means we found a lower price
When max_profit updates, it means we found a higher sp in future if it doesnt update it was in the past

Question 3

Majority Element

Problem: Given an array nums of size n, return the majority element (the element that appears more than ⌊n / 2⌋ times). You may assume that the majority element always exists in the array.
Example: Input: [3, 3, 4, 2, 2, 2, 2, 2, 2]; Output: 2

Answer 3

The intuition behind the solution comes from the understanding that if an element occurs more than n / 2 times, it means that element is present more often than all other elements combined. For every instance of a non-majority element, there must be more instances of the majority element. We can use this intuition with a clever algorithm known as the Moore Voting Algorithm.

The Moore Voting Algorithm works by keeping a current candidate for majority element and a counter. As it goes through the array, the algorithm either increases the count if the current number matches the candidate or decreases the count otherwise. When the count reaches zero, it means that up to that point, there is no majority element, and the algorithm selects the current number as the new candidate. The key insight is that the majority element’s surplus count will withstand the count decrements due to non-majority elements.

1. Initialization: Start with the assumption that the first element of the array is the majority element and initialize a count to 1.
2. Iterate through the array: Loop through the array from the second element onward.
3. Update count and candidate:
   
   • If the current element is equal to the candidate, increment the count.
   • If the current element is different from the candidate, decrement the count.
   • If the count becomes zero, update the candidate to the current element, and reset the count to 1.
4. Result:
   By the end of the iteration, the candidate should be the majority element.

Question 4

longest consecutive sequence

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.

Answer 4

public int longestConsecutive(int[] nums) {
…
}
The method takes an array of integers nums and returns an integer representing the length of the longest consecutive sequence.

HashSet<Integer> numSet = new HashSet<>();
for (int num : nums) {
numSet.add(num);
}
A HashSet named numSet is created to store all the elements from the input array nums.
Using a HashSet allows for O(1) average time complexity for checking if an element is present in the set.
All elements from nums are added to the numSet.</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);
} } A variable longestStreak is initialized to 0 to keep track of the longest consecutive sequence found. The outer loop iterates over each element num in the array nums. The condition if (!numSet.contains(num - 1)) checks if the current number is the start of a new sequence. This is done by checking if there is no number just before num in the set. If num - 1 is not in the set, then num is the start of a new sequence. If num is the start of a new sequence: currentNum is initialized to num. currentStreak is initialized to 1. The inner while loop while (numSet.contains(currentNum + 1)) continues to check and count the consecutive numbers: currentNum is incremented by 1. currentStreak is incremented by 1 for each consecutive number found. After the inner while loop ends, longestStreak is updated to the maximum of its current value or currentStreak.

return longestStreak;
The method returns longestStreak, which is the length of the longest consecutive sequence found in the array nums.

nums = [100, 4, 200, 1, 3, 2]
HashSet:
numSet = [100, 4, 200, 1, 3, 2] (the elements can be in any order as it is a set)
Iterations:

First Element (num = 100):
Condition: !numSet.contains(100 - 1) → !numSet.contains(99) → True
currentNum = 100
currentStreak = 1
Inner while loop: numSet.contains(100 + 1) → numSet.contains(101) → False
longestStreak = Math.max(longestStreak, currentStreak) → longestStreak = Math.max(0, 1) → longestStreak = 1

Second Element (num = 4):
Condition: !numSet.contains(4 - 1) → !numSet.contains(3) → False

Third Element (num = 200):
Condition: !numSet.contains(200 - 1) → !numSet.contains(199) → True
currentNum = 200
currentStreak = 1
Inner while loop: numSet.contains(200 + 1) → numSet.contains(201) → False
longestStreak = Math.max(longestStreak, currentStreak) → longestStreak = Math.max(1, 1) → longestStreak = 1

Fourth Element (num = 1):
Condition: !numSet.contains(1 - 1) → !numSet.contains(0) → True
currentNum = 1
currentStreak = 1
Inner while loop:
numSet.contains(1 + 1) → numSet.contains(2) → True
currentNum = 2
currentStreak = 2
numSet.contains(2 + 1) → numSet.contains(3) → True
currentNum = 3
currentStreak = 3
numSet.contains(3 + 1) → numSet.contains(4) → True
currentNum = 4
currentStreak = 4
numSet.contains(4 + 1) → numSet.contains(5) → False
longestStreak = Math.max(longestStreak, currentStreak) → longestStreak = Math.max(1, 4) → longestStreak = 4

Question 5

Longest consecutive sequence

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.

Answer 5

1. 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.

Step-by-Step Explanation:

1.	Adding Elements to HashSet:
*	By adding all elements to the HashSet, we ensure that checking for the presence of any element in the array is done in constant time.
2.	Identifying the Start of Sequences:
*	For each element in the array, we check if it is the start of a sequence. An element is considered the start if there is no preceding element (i.e., num - 1 is not in the HashSet).
3.	Counting the Sequence Length:
*	Once a start of a sequence is identified, we count its length by checking the presence of consecutive elements (num + 1, num + 2, etc.) in the HashSet.
4.	Updating the Longest Sequence Length:
*	We keep track of the maximum sequence length encountered during the iterations.

Question 6

coin change

Answer 6

public int coinChange(int[] coins, int amount) {
…
}
The method takes two parameters: an array of integers coins representing different coin denominations and an integer amount representing the total amount of money.

int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
An array dp is created to store the minimum number of coins needed to make each amount from 0 to amount.
The array is initialized with a value of amount + 1 (an impossible high value to represent that initially, all amounts are considered unreachable).
dp[0] is set to 0 because no coins are needed to make the amount 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);
}
}
}
Two nested loops are used:
The outer loop iterates over each amount i from 1 to amount.
The inner loop iterates over each coin in the coins array.
For each i, the code checks if the coin value coin is less than or equal to i (the current amount).
If the coin can be used to make the amount i, the code updates dp[i] to the minimum of its current value or dp[i - coin] + 1.
dp[i - coin] + 1 represents using one more coin to make the amount i.

return dp[amount] > amount ? -1 : dp[amount];
After filling the dp array, the method checks if dp[amount] is still greater than amount.
If it is, it means that it is not possible to make the amount with the given coins, so the method returns -1.
Otherwise, it returns dp[amount], which is the minimum number of coins needed to make the amount.

Input:
coins = [1, 2, 5]
amount = 11
Initial DP Array:
dp = [0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12] (all values initialized to amount + 1, which is 12)
Iterations:
For i = 1:

coin = 1:
dp[1] = Math.min(dp[1], dp[1 - 1] + 1) = Math.min(12, 0 + 1) = 1
coin = 2 and coin = 5 are skipped because they are greater than i.
dp = [0, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
For i = 2:

coin = 1:
dp[2] = Math.min(dp[2], dp[2 - 1] + 1) = Math.min(12, 1 + 1) = 2
coin = 2:
dp[2] = Math.min(dp[2], dp[2 - 2] + 1) = Math.min(2, 0 + 1) = 1
coin = 5 is skipped because it is greater than i.
dp = [0, 1, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12]

Question 7

length of longest subsequence

nput: 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.

Answer 7

public int lengthOfLIS(int[] nums) {
…
}
The method takes an array of integers nums and returns an integer representing the length of the longest increasing subsequence.

if (nums == null || nums.length == 0) {
return 0;
}
This checks if the input array nums is null or has a length of 0. If either condition is true, it returns 0 because there are no elements to form a subsequence.

int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int maxLength = 1;
An array dp is created to store the length of the longest increasing subsequence that ends at each index.
The dp array is initialized with 1 because the minimum length of an increasing subsequence that ends at any index is 1 (the element itself).
A variable maxLength is initialized to 1 to keep track of the maximum length of any increasing subsequence found.

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]);
}
Two nested loops are used:
The outer loop iterates over each element in nums starting from the second element (i = 1).
The inner loop iterates over each element before the current element (j = 0 to i-1).
For each pair (i, j), the code checks if nums[j] < nums[i] to ensure that the subsequence is increasing.
If the condition is true, dp[i] is updated to the maximum of its current value or dp[j] + 1.
dp[j] + 1 represents the length of the longest increasing subsequence that ends at j extended by the element at i.
After updating dp[i], maxLength is updated to the maximum of its current value or dp[i].

return maxLength;
The method returns maxLength, which is the length of the longest increasing subsequence found in the array nums.

Why dp[i - coin]?
When calculating dp[i], you need to consider the effect of adding each coin denomination to the solution. The idea is to build up the solution for amount i by considering how you can get there from previous amounts.

Formula:
java
Copy code
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
Current Amount (i):

You want to determine the minimum number of coins needed to make the amount i.
Previous Amount (i - coin):

If you have already computed the minimum number of coins needed to make the amount i - coin, you can use this result to help compute the minimum number of coins for amount i.
Specifically, if you can make i - coin using dp[i - coin] coins, then you can make i by adding one more coin (the coin itself) to this amount.
Updating dp[i]:

dp[i] = Math.min(dp[i], dp[i - coin] + 1);
This means: “The minimum number of coins needed to make amount i is either the current known minimum (dp[i]) or the number of coins needed to make amount i - coin plus one more coin.”
Example Walkthrough

Input:
nums = [10, 9, 2, 5, 3, 7, 101, 18]
Initial DP Array:
dp = [1, 1, 1, 1, 1, 1, 1, 1] (all values initialized to 1)
maxLength = 1
Iterations:
For i = 1 (nums[1] = 9):[10, 9, 2, 5, 3, 7, 101, 18]
j = 0 (nums[0] = 10):
Condition: nums[0] < nums[1] → 10 < 9 → False
dp = [1, 1, 1, 1, 1, 1, 1, 1]
maxLength = 1

For i = 2 (nums[2] = 2):[10, 9, 2, 5, 3, 7, 101, 18]
j = 0 (nums[0] = 10):
Condition: nums[0] < nums[2] → 10 < 2 → False
j = 1 (nums[1] = 9):
Condition: nums[1] < nums[2] → 9 < 2 → False
dp = [1, 1, 1, 1, 1, 1, 1, 1]
maxLength = 1

For i = 3 (nums[3] = 5):[10, 9, 2, 5, 3, 7, 101, 18]
j = 0 (nums[0] = 10):
Condition: nums[0] < nums[3] → 10 < 5 → False
j = 1 (nums[1] = 9):
Condition: nums[1] < nums[3] → 9 < 5 → False
j = 2 (nums[2] = 2):
Condition: nums[2] < nums[3] → 2 < 5 → True
Update: dp[3] = Math.max(dp[3], dp[2] + 1) → dp[3] = Math.max(1, 1 + 1) → dp[3] = 2
dp = [1, 1, 1, 2, 1, 1, 1, 1]
maxLength = 2
… and so on until i = 7.

Question 8

two sum

Answer 8

public int[] twoSum(int[] nums, int target) {
…
}
}
The Solution class contains a method twoSum which takes an array of integers nums and an integer target, and returns an array of two integers representing the indices of the two numbers that add up to the target.

HashMap Initialization
java
Copy code
HashMap<Integer, Integer> map = new HashMap<>();
A HashMap named map is created to store each number in nums as the key and its corresponding index as the value.

Iterating Through the Array
java
Copy code
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);
}
A for loop iterates over each element in the nums array.
For each element nums[i], the complement is calculated as target - nums[i].
The method checks if the complement exists in the map using map.containsKey(complement).
If it does, it means that the current number nums[i] and the complement add up to the target. The indices of these two numbers are returned as a new array: return new int[]{map.get(complement), i}.
If the complement is not found in the map, the current number and its index are added to the map using map.put(nums[i], i).

Exception Handling
java
Copy code
throw new IllegalArgumentException(“No two sum solution”);
If the loop completes without finding a valid pair, an IllegalArgumentException is thrown with the message “No two sum solution”.

Input:
nums = [2, 7, 11, 15]
target = 9
Iterations:
First Iteration (i = 0, nums[0] = 2):

complement = 9 - 2 = 7
map.containsKey(7) → False
map.put(2, 0) → map = {2=0}
Second Iteration (i = 1, nums[1] = 7):

complement = 9 - 7 = 2
map.containsKey(2) → True
Return indices: return new int[]{map.get(2), 1} → return new int[]{0, 1}