Arrays

Question 1

how to insert an element in a array ?

Answer 1

there are two ways to insert an element in a array.
1. add an element ‘element’ at k position. In this case you have to first check if the index k is smaller than the length of the array. then you can easily add the element at arr[k] = element; after shifting all the elements to the right.
2. add an element at the end of the array: In this case, first check if the postion at which you want to add the element is not greater than the length of the array. then just add the element at arr[pos] = element;

Question 2

How to rotate an array. Explain the approach using temp array.

Answer 2

1. first, make a temp array of size equal to the original array.
2. Then, copy all the elements from the d(the index from which to rotate the array) to n-1 in the temp array and also keep an variable k to keep track of the last index in the temp array.
3. Now only d elements are left in the original array. copy all the leftout elements to the temp array from the index 0 to d. add elements from the index k to the end of the original array.
4. copy the elements from temp array to original array if you want or just return the temp array.

time: O(n)
space: O(n)

Question 3

how to rotate an array by rotating elements one by one ?

Answer 3

1. In this approach, first you have to keep an variable to track the first element in the array and then left shift all the elements of the array.
2. Then, simply add the variable to the last of the array.
3. Repeat this whole process for d times.
4. it will take two nested loops to work. Outer loop will keep the track of d and inner loop is for the shifting.

time: O(n*d)
space: O(1)

Question 4

how to rotate an array using the juggling algorithm ?

Answer 4

1. Make a reverse method that can reverse the elements of an array. This method takes three arguments:
   
   • the array on which the reverse operation to be performed
   • The starting index
   • The ending index
2. Now, first reverse the elements starting from 0 to d-1.
3. Then, reverse the elements from d to n-1.
4. Lastly, reverse the whole array i.e, from 0 to n-1.
   The final array is the result after rotating the array by d elements.

time: O(n)
space: O(1)

Question 5

how to reverse an array iteratively ?

Answer 5

1) Initialize start and end indexes as
start = 0, end = N-1
2) In a loop, swap arr[start] with arr[end]
and change start and end as follows :
start = start + 1,
end = end – 1

time: O(N)
space: constant

Question 6

how to reverse an array recursively ?

Answer 6

1) Initialize start and end indexes as
start = 0, end = n-1
2) Swap arr[start] with arr[end]
3) Recursively call reverse for rest of the array. for eg.
return reverse(arr, start + 1, end - 1)

time: O(N)
space: constant

Question 7

what is the purpose of using sliding window technique ? or in which situation we use this technique ?

Answer 7

This technique shows how a nested for loop in few problems can be converted to single for loop and hence reducing the time complexity.

Question 8

how sliding window technique works ?

Answer 8

This technique works in 3 simple steps:
I am demostrating this technique by solving an max sum for k consecutive elements in a array problem.
In this problem, k is the length of sub array for which we have to calculate the sum of elements.
The following steps demostrate the sliding window technique-
1. first, we will calculate the sum of first k elements for which we will iterate from 0 to k and store the sum of elements in window_sum.
2. Then, we will make an element maxSum for tracking the max sum of elements in the array. Now, we will remove the last element after shifting the window to the left and add the latest element to the sum. The current sum would look something like this
currentSum += arr[i] + arr[i -k]
3. Lastly, we will compare the current sum with the max sum that we were keeping for checking the max sum of consecutive elements in an array.

time: O(n)
space: constant

Question 9

How to find the second largest element in an array ?

Answer 9

Firstly, we should find the largest element in the array and then find the second largest element by just excluding the largest element. we can find the largest and second largest in the same traversal of the array.

The condition to find the second largest is:
if (inputArray[index] != largest)

Question 10

How to move zeros to the end in an array ?

Answer 10

To move zeros to the end in an array, we can use two pointer approach
* First pointer will keep track of the non zero elements present in the array and increment only when it encounters a non zero element.
* Second pointer will simply traverse the array and will help in overriding the zero elements to the non zero elements.
* After the whole traversal, the first pointer will become the 1st index for the zero elements present in the array, so we will simply override all the remaining elements by zero.

time: O(N)
space: constant

Question 11

how to insert an element in the middle of an array ?

Answer 11

To insert an element in the middle of an array, first you have to move all the elements to the right(only if the capacity is not full otherwise just return the original array)

for moving the elements to the right, traverse the array in reverse direction and override the right element to the left element and stop the iteration at the position on which the new element will be inserted

inserting at the end, time: 1
inserting at the begining, time: n
in general insertion time: n

Question 12

what is the time complexity of insert at the end for a dynamic sized array ?

Answer 12

In general, it is O(1)

Question 13

time complexity for inserting in an array ?

Answer 13

O(N)

Question 14

time complexity for searching in an unsorted array ?

Answer 14

O(N)

Question 15

Time complexity for searching in an sorted array ?

Answer 15

O(logn)

Question 16

time complexity for deletion in an array ?

Answer 16

O(N)

Question 17

time complexity to get and update an ith element in an array ?

Answer 17

O(1)

Question 18

time complexity for insertion and deletion from the end in an array ?

Answer 18

O(1)

Question 19

how to find immediate greater element than x in an array ?

Answer 19

1. first, we make a variable called currentImmediateGreater and set a large value to it.
2. Then we will iterate the whole array and check whether currentImmediateGreater is greater that ith element as well as x(the element to check). The condition will look something like this:

if (inputArray[i] > x 
&& currentImmediateGreater > inputArray[i])

After checking this condition, we will simple re initialize the currentImmediateGreater with inputArray[i] found.

Question 20

find the majoritGiven an array arr[] of size N and two elements x and y, use counter variables to find which element appears most in the array. If both elements have the same frequency, then return the smaller element.
Note: We need to return the element, not its count.y between two elements x and y

Answer 20

1. First, make a counter variable to count the number of occurances for both the elements in the array
2. if x is encountered then increament the counter and if y is encountered then decreament the counter.
3. if counter is positive then, it means x occured more than y and vice versa.
4. if counter is zero then, it means both the elements have same occurance and we will return the smallest among them

Question 21

how to find max and min element in a array ?

Answer 21

1. first, assume arr[0] as the max or min element
2. traverse the array and compare the current element with the max element, if the current element is greater than maxElement then, assign maxElement with the current element
3. do the same for minElement

Question 22

how to reverse an array without using temporary array?

Answer 22

1. for this we will first make a temporary variable temp and use it swap the elements in the array
2. we will traverse the array to it’s half size and keep swapping the elements until we reach the half the length

Question 23

how to check if a char array is palindrome or not using recursion ?

Answer 23

There would be three conditions to check whether the array is palindrome or not.

1. check if there is only one character in the array, it means it is palindrome
2. check if the first and last character matches or not, if not then it is not palindrome
3. check the substring or subarray by calling the method recusively as
   ~~~
   checkPalindrome(string[], start + 1, end - 1)
   ~~~

Question 24

Give brute force solution

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.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Answer 24

Approach 1: Brute Force
Algorithm

The brute force approach is simple. Loop through each element x and find if there is another value that equals to target−x.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        // If no valid pair is found, return an empty array instead of null
        return new int[] {};
    }
}

Complexity Analysis

Time complexity: O(n
2
).
For each element, we try to find its complement by looping through the rest of the array which takes O(n) time. Therefore, the time complexity is O(n
2
).

Space complexity: O(1).
The space required does not depend on the size of the input array, so only constant space is used.

Question 25

# Give a solution which works with O(n) time complexity. 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. Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]. Example 2: Input: nums = [3,2,4], target = 6 Output: [1,2] Example 3: Input: nums = [3,3], target = 6 Output: [0,1] Constraints: 2 <= nums.length <= 104 -109 <= nums[i] <= 109 -109 <= target <= 109 Only one valid answer exists.

Answer 25

Approach 2: Two-pass Hash Table Intuition To improve our runtime complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to get its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table. We can reduce the lookup time from O(n) to O(1) by trading space for speed. A hash table is well suited for this purpose because it supports fast lookup in near constant time. I say "near" because if a collision occurred, a lookup could degenerate to O(n) time. However, lookup in a hash table should be amortized O(1) time as long as the hash function was chosen carefully. Algorithm A simple implementation uses two iterations. In the first iteration, we add each element's value as a key and its index as a value to the hash table. Then, in the second iteration, we check if each element's complement (target−nums[i]) exists in the hash table. If it does exist, we return current element's index and its complement's index. Beware that the complement must not be nums[i] itself! ``` class Solution { public int[] twoSum(int[] nums, int target) { Map map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement) && map.get(complement) != i) { return new int[] { i, map.get(complement) }; } } // In case there is no solution, return an empty array return new int[] {}; } } ``` Complexity Analysis Time complexity: O(n). We traverse the list containing n elements exactly twice. Since the hash table reduces the lookup time to O(1), the overall time complexity is O(n). Space complexity: O(n). The extra space required depends on the number of items stored in the hash table, which stores exactly n elements.

Question 26

# 169. Majority Element, solve with naiva approach 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 Constraints: n == nums.length 1 <= n <= 5 * 104 -109 <= nums[i] <= 109

Answer 26

Approach 1: Sorting Intuition: The intuition behind this approach is that if an element occurs more than n/2 times in the array (where n is the size of the array), it will always occupy the middle position when the array is sorted. Therefore, we can sort the array and return the element at index n/2. ``` class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); int n = nums.length; return nums[n/2]; } } ```

Question 27

# 169. Majority Element, solve with O(n) time 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 Constraints: n == nums.length 1 <= n <= 5 * 104 -109 <= nums[i] <= 109

Answer 27

Approach 2: Hash Map Intuition: The intuition behind using a hash map is to count the occurrences of each element in the array and then identify the element that occurs more than n/2 times. By storing the counts in a hash map, we can efficiently keep track of the occurrences of each element. ``` class Solution { public int majorityElement(int[] nums) { int n = nums.length; Map map = new HashMap<>(); for (int i = 0; i < n; i++) { map.put(nums[i], map.getOrDefault(nums[i], 0) + 1); } n = n / 2; for (Map.Entry entry : map.entrySet()) { if (entry.getValue() > n) { return entry.getKey(); } } return 0; } } ```

Question 28

# optimised approach Merge Two sorted arrays: You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively. Merge nums1 and nums2 into a single array sorted in non-decreasing order. The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n. Example 1: Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1. Example 2: Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Explanation: The arrays we are merging are [1] and []. The result of the merge is [1]. Example 3: Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1] Explanation: The arrays we are merging are [] and [1]. The result of the merge is [1]. Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1. Constraints: nums1.length == m + n nums2.length == n 0 <= m, n <= 200 1 <= m + n <= 200 -109 <= nums1[i], nums2[j] <= 109

Answer 28

Approach : Two Pointer We can start with two pointers i and j, initialized to m-1 and n-1, respectively. We will also have another pointer k initialized to m+n-1, which will be used to keep track of the position in nums1 where we will be placing the larger element. Then we can start iterating from the end of the arrays i and j, and compare the elements at these positions. We will place the larger element in nums1 at position k, and decrement the corresponding pointer i or j accordingly. We will continue doing this until we have iterated through all the elements in nums2. If there are still elements left in nums1, we don't need to do anything because they are already in their correct place. ``` class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1; int j = n - 1; int k = m + n - 1; while (j >= 0) { if (i >= 0 && nums1[i] > nums2[j]) { nums1[k--] = nums1[i--]; } else { nums1[k--] = nums2[j--]; } } } } ```

Question 29

# Majority element solve with best approach 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 Constraints: n == nums.length 1 <= n <= 5 * 104 -109 <= nums[i] <= 109

Answer 29

Approach 3: Moore Voting Algorithm Intuition: The intuition behind the Moore's Voting Algorithm is based on the fact that if there is a majority element in an array, it will always remain in the lead, even after encountering other elements. Explanation: Algorithm: Initialize two variables: count and candidate. Set count to 0 and candidate to an arbitrary value. Iterate through the array nums: a. If count is 0, assign the current element as the new candidate and increment count by 1. b. If the current element is the same as the candidate, increment count by 1. c. If the current element is different from the candidate, decrement count by 1. After the iteration, the candidate variable will hold the majority element. Explanation: The algorithm starts by assuming the first element as the majority candidate and sets the count to 1. As it iterates through the array, it compares each element with the candidate: a. If the current element matches the candidate, it suggests that it reinforces the majority element because it appears again. Therefore, the count is incremented by 1. b. If the current element is different from the candidate, it suggests that there might be an equal number of occurrences of the majority element and other elements. Therefore, the count is decremented by 1. Note that decrementing the count doesn't change the fact that the majority element occurs more than n/2 times. If the count becomes 0, it means that the current candidate is no longer a potential majority element. In this case, a new candidate is chosen from the remaining elements. The algorithm continues this process until it has traversed the entire array. The final value of the candidate variable will hold the majority element. Explanation of Correctness: The algorithm works on the basis of the assumption that the majority element occurs more than n/2 times in the array. This assumption guarantees that even if the count is reset to 0 by other elements, the majority element will eventually regain the lead. Let's consider two cases: If the majority element has more than n/2 occurrences: The algorithm will ensure that the count remains positive for the majority element throughout the traversal, guaranteeing that it will be selected as the final candidate. If the majority element has exactly n/2 occurrences: In this case, there will be an equal number of occurrences for the majority element and the remaining elements combined. However, the majority element will still be selected as the final candidate because it will always have a lead over any other element. In both cases, the algorithm will correctly identify the majority element. The time complexity of the Moore's Voting Algorithm is O(n) since it traverses the array once. This approach is efficient compared to sorting as it requires only a single pass through the array and does not change the original order of the elements. ``` class Solution { public int majorityElement(int[] nums) { int count = 0; int candidate = 0; for (int num : nums) { if (count == 0) { candidate = num; } if (num == candidate) { count++; } else { count--; } } return candidate; } } ```

Question 30

# 169. Majority Element solve with nlogn time 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 Constraints: n == nums.length 1 <= n <= 5 * 104 -109 <= nums[i] <= 109

Answer 30

Approach 1: Sorting Intuition: The intuition behind this approach is that if an element occurs more than n/2 times in the array (where n is the size of the array), it will always occupy the middle position when the array is sorted. Therefore, we can sort the array and return the element at index n/2. Explanation: The code begins by sorting the array nums in non-decreasing order using the sort function from the C++ Standard Library. This rearranges the elements such that identical elements are grouped together. Once the array is sorted, the majority element will always be present at index n/2, where n is the size of the array. This is because the majority element occurs more than n/2 times, and when the array is sorted, it will occupy the middle position. The code returns the element at index n/2 as the majority element. The time complexity of this approach is O(n log n) since sorting an array of size n takes O(n log n) time. ``` class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); int n = nums.length; return nums[n/2]; } } ```

Question 31

# 53. Maximum Subarray, solve in O(n) time and O(1) space Given an integer array nums, find the subarray with the largest sum, and return its sum. Example 1: Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: The subarray [4,-1,2,1] has the largest sum 6. Example 2: Input: nums = [1] Output: 1 Explanation: The subarray [1] has the largest sum 1. Example 3: Input: nums = [5,4,-1,7,8] Output: 23 Explanation: The subarray [5,4,-1,7,8] has the largest sum 23. Constraints: 1 <= nums.length <= 105 -104 <= nums[i] <= 104

Answer 31

We will use kadane's algorithm, Intuition The Intuition behind the code is to find the maximum sum of a contiguous subarray within the given array nums. It does this by scanning through the array and keeping track of the current sum of the subarray. Whenever the current sum becomes greater than the maximum sum encountered so far, it updates the maximum sum. If the current sum becomes negative, it resets the sum to 0 and starts a new subarray. By the end of the loop, the code returns the maximum sum found. Approach: We start by initializing two variables: maxSum and currentSum. maxSum represents the maximum sum encountered so far and is initially set to the minimum possible integer value to ensure that any valid subarray sum will be greater than it. currentSum represents the current sum of the subarray being considered and is initially set to 0. We iterate through the nums array using a for loop, starting from the first element and going up to the last element. For each element in the array, we add it to the current sum currentSum. This calculates the sum of the subarray ending at the current element. Next, we check if the current sum currentSum is greater than the current maximum sum maxSum. If it is, we update maxSum with the new value of currentSum. This means we have found a new maximum subarray sum. If the current sum currentSum becomes negative, it indicates that including the current element in the subarray would reduce the overall sum. In such cases, we reset currentSum to 0. This effectively discards the current subarray and allows us to start a fresh subarray from the next element. We repeat steps 3 to 5 for each element in the array. After iterating through the entire array, the variable maxSum will contain the maximum subarray sum encountered. Finally, we return the value of maxSum as the result, representing the maximum sum of a contiguous subarray within the given array nums. ``` class Solution { public int maxSubArray(int[] nums) { int maxSum = Integer.MIN_VALUE; int currentSum = 0; for (int i = 0; i < nums.length; i++) { currentSum += nums[i]; if (currentSum > maxSum) { maxSum = currentSum; } if (currentSum < 0) { currentSum = 0; } } return maxSum; } } ```

Question 32

# 189. Rotate Array, solve with naive approach Given an integer array nums, rotate the array to the right by k steps, where k is non-negative. Example 1: Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4] Example 2: Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100] Constraints: 1 <= nums.length <= 105 -231 <= nums[i] <= 231 - 1 0 <= k <= 105

Answer 32

Got TLE ``` class Solution { public void rotate(int[] nums, int k) { for (int i = 0; i < k; i++) { rotateOnce(nums); } } public void rotateOnce(int[] nums) { int n = nums.length; int last = nums[n - 1]; for (int i = n - 1; i > 0; i--) { nums[i] = nums[i - 1]; } nums[0] = last; } } ```

Question 33

# 189. Rotate Array, solve with O(n) time and O(1) space Given an integer array nums, rotate the array to the right by k steps, where k is non-negative. Example 1: Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4] Example 2: Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100] Constraints: 1 <= nums.length <= 105 -231 <= nums[i] <= 231 - 1 0 <= k <= 105

Answer 33

Approach First, it calculates the effective rotation amount by taking the modulus of k with the length of the array, ensuring that k is within the range of the array length. Then, it calls the reverse function three times: First, it reverses the entire array, effectively placing the last k elements at the start of the array. Second, it reverses the first k elements, moving them to the end of the array. Finally, it reverses the remaining elements, restoring the original order of the array with the elements rotated to the right by k steps. ``` class Solution { public void rotate(int[] nums, int k) { k %= nums.length; reverse(nums, 0, nums.length-1); reverse(nums, 0, k-1); reverse(nums, k, nums.length-1); } public void reverse(int[] nums, int start, int end){ while(start < end){ int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; start++; end--; } } } ```

Question 34

# 121. Best Time to Buy and Sell Stock, solve in O(n) time and O(1) space 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. Example 2: Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0. Constraints: 1 <= prices.length <= 105 0 <= prices[i] <= 104

Answer 34

Intuition The problem aims to find the maximum profit that can be obtained by buying and selling a stock. The given solution seems to follow a simple approach of iterating through the prices, keeping track of the minimum buying price, and updating the profit whenever a higher selling price is encountered. Approach Initialize variables buy with the first element of the prices array and profit as 0. Iterate through the prices starting from the second element. Update the buy variable if the current price is lower than the current buying price. Update the profit if the difference between the current price and the buying price is greater than the current profit. Return the final profit. Kadane's Algorithm Kadane's Algorithm is a dynamic programming technique used to find the maximum subarray sum in an array of numbers. The algorithm maintains two variables: max_current represents the maximum sum ending at the current position, and max_global represents the maximum subarray sum encountered so far. At each iteration, it updates max_current to include the current element or start a new subarray if the current element is larger than the accumulated sum. The max_global is updated if max_current surpasses its value. Relating with the Approach In the provided approach for finding the maximum profit in stock prices, the algorithm can be seen as a variation of Kadane's Algorithm. Instead of finding the maximum subarray sum directly, it focuses on finding the maximum positive difference between consecutive elements (prices) in the array. Here's how the approach relates to Kadane's Algorithm: Initialization: In Kadane's Algorithm, max_current and max_global are initialized to the first element of the array. In the stock profit approach, buy is initialized with the first element of the prices array, and profit is initialized to 0. Iteration: Kadane's Algorithm iterates through the array, updating max_current based on the current element's value and deciding whether to start a new subarray. The stock profit approach iterates through the prices array, updating buy when a lower price is encountered and treating the difference between the current price and buy as a potential profit. Comparison and Update: Kadane's Algorithm compares and updates max_current and max_global at each iteration. The stock profit approach compares and updates profit whenever a positive difference between the current price and buy exceeds the current profit. ``` class Solution { public int maxProfit(int[] prices) { int buyPrice = prices[0]; int profit = 0; for (int i = 1; i < prices.length; i++) { int currentPrice = prices[i]; if (currentPrice < buyPrice) { buyPrice = currentPrice; } else if (currentPrice - buyPrice > profit) { profit = currentPrice - buyPrice; } } return profit; } } ```

Question 35

# 122. Best Time to Buy and Sell Stock II, solve in O(n) time and O(1) spa You are given an integer array prices where prices[i] is the price of a given stock on the ith day. On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve. Example 1: Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7. Example 2: Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Total profit is 4. Example 3: Input: prices = [7,6,4,3,1] Output: 0 Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0. Constraints: 1 <= prices.length <= 3 * 104 0 <= prices[i] <= 104

Answer 35

Intuition 👈 In the given problem, we are provided with an array named "prices," where prices[i] represents the current price of a stock on day i. The task is to determine the maximum profit that can be achieved from selling the stock. Approach 👈 To solve this question we will use Greedy Algorithm. Now if you don't know anything about Greedy algorithm here is the small explanation of the Greedy. Greedy algorithms are a class of algorithms that make locally optimal choices at each step with the hope of finding a global optimum solution. In these algorithms, decisions are made based on the information available at the current moment without considering the consequences of these decisions in the future. The key idea is to select the best possible choice at each step, leading to a solution that may not always be the most optimal but is often good enough for many problems. Code Explanation 👈 Variable Initialization: max is initialized to 0. This variable will accumulate the maximum profit throughout the iteration. start is initialized to prices[0], the price of the stock on the first day. This variable represents the buying price of the stock. len is initialized to prices.length, the length of the prices array, representing the total number of days. Iteration: A for loop iterates through the prices array starting from the second element (i = 1) to the end of the array (i < len). This loop is used to calculate the profit for each transaction. Profit Calculation: Within the loop, there's an if statement checking if the current price (prices[i]) is greater than the buying price (start). If true, it indicates a potential profit opportunity. The difference between the current price and the buying price (prices[i] - start) is calculated and added to max. This step simulates selling the stock bought at start price, capturing the profit, and then considering the current price as a new buying price for potential future transactions. Regardless of whether a profit was made or not, the start is updated to the current price (prices[i]). This step prepares for the next iteration, considering the current day's price as the new buying price. Return Statement: After the loop finishes executing, the method returns the accumulated max value, which represents the maximum profit that could have been achieved based on the given stock prices. ``` class Solution { public int maxProfit(int[] prices) { int buy = prices[0]; int profit = 0; int profitSum = 0; for (int i = 0; i < prices.length; i++) { if (buy < prices[i]) { profit += prices[i] - buy; } buy = prices[i]; } return profit; } } ```

Question 36

# 55. Jump Game, solve in O(n) time and O(1) space You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise. 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. Constraints: 1 <= nums.length <= 104 0 <= nums[i] <= 105

Answer 36

Intuition The basic idea is this: at each step, we keep track of the furthest reachable index. The nature of the problem (eg. maximal jumps where you can hit a range of targets instead of singular jumps where you can only hit one target) is that for an index to be reachable, each of the previous indices have to be reachable. Approach Hence, it suffices that we iterate over each index, and If we ever encounter an index that is not reachable, we abort and return false. By the end, we will have iterated to the last index. If the loop finishes, then the last index is reachable. ``` class Solution { public boolean canJump(int[] nums) { int reachable = 0; for(int i = 0; i < nums.length; i ++) { if(i > reachable) return false; reachable = Math.max(reachable, i + nums[i]); } return true; } } ```