Arrays

Kadane’s Algortihm

• Kadane's algorithm is a greedy/dynamic programming algorithm that can be used on array problems to bring the time complexity down to O(n). It is used to calculate the maximum sum subarray ending at a particular position.

• The key idea is to do only one pass, to find some logic in the array that allows us to do this. This maybe two points, dropping anything that’s negative, restarting the subarray once our sum is below 0, etc.

• Example: Q: Find a non-empty subarray with the largest sum.

• Answer: (After the brute force approach of O(n**2)

  

• Kadanes Algorithm Sliding Window Variation

  • Return the Indexes of subarray in the above question
  • You basically want to keep a window where left never really crosses the right.
  • As you add 1 value from the right, IF some condition is met, you can REMOVE a value from the left.. and move on.
    • Or you can keep it there aswell, until you need to jump all the way forward where R = L
    • It all depends on a case to case (problem to problem) bases, what the logic should be
  • Sliding window: can Grow in size, becoming smaller, staying the same size or even

Sliding Window

• Useful for when arrays / linked lists are sorted, etc.

• Two pointers is a more general version of sliding window where the pointers can cross each other and can be on different arrays.

  

• Commonalities:

  • Everything grouped sequentially
  • longest, smallest, contains,sub-string, permutations, maximize, minimize something… All can use sliding window

• To get the window size: end - start + 1, or right - left + 1

• This is usually O(n) for both cases. In Case 3, you’d have an DS along with it, such as hashmap, or set above, but no worries. Think about looping 2x too.

• When to use:

  • Whenever you need to calculate a running average
  • If you want to formulate a set of adjacent pairs
  • The problem involves an ordered data structure
  • If you need to identify a target value in an array
  • If you need to identify a longest, shortest, or most optimal sequence that satisfies a given condition in a collection

Algorithm:

1. Use two pointers: start and end to represent a window.
2. Move end to find a valid window.
3. When a valid window is found, move start (remember to remove the start value, or to get the window length) to find a smaller window.

Implementation (Fixed Length):

def MaxSumSubarray(arr, k):
	start, end = 0, k - 1
	subarray = 0
  max_val = 0

	for i in range(0, len(arr)):
		subarray += arr[i]
		if i >= end:
			max_val = max(subarray, max_val)
			subarray -= arr[start]
			start += 1
	return max_val

# If the len(set) <= 2
    if len(set) < 3:
      my_set.add(fruits[i])
      count += 1

    if fruits[i] not in chars:
      # Check the lenght of the set
      if len(my_set) < 2:
        my_set.add(fruits[i])

    chars.add(fruits[i])
    while chars[]

  # TODO: Write your code here
  
  # Approach 1: Brute Force
  # Double for loop, stop second loop when the len ( set(chars) ) > 2. 
  # Time Complexity: O(n^2)
  count = 0
  max_count = -1
  for i in range(len(fruits)-1):
    current_fruits = []
    current_fruits.append(fruits[i])

    for j in range(i+1, len(fruits)):
      
      if len(set(current_fruits)) <= 2:
        current_fruits.append(fruits[i])
      
      else:
        # How many fruits are in the basket?
        count = len(current_fruits)
        max_count = max(max_count, count)

  return max_count

# Approach 2:
  # Sliding window
  start = 0
  basket = []
  count, max_count = 0, -1
  my_set =  set()
  # loop over the elements
  for i in range(len(fruits)):
    my_set.add(fruits[i])
    if fruits[i] in my_set and len(my_set) <= 2:
      count += 1
    else:
      # remove the last element 
      count -= 1
      max_count = max(count, max_count)
      i = start
      start += 1
  return max_count

Implementation (Dynamic Length):

def lengthOfLongestSubstring(self, s: str) -> int:
        chars = set()
        left = 0
        max_count  = 0
              
        # loop thru the string
        for right in range(len(s)):
            
            # Once we find a repeating char..
            while s[right] in chars:
                # count the length of substr
                # Remove the left most character
                chars.remove(s[left])
                left += 1
            
            # If no repeating character..
            chars.add(s[right])
            # Max of max_count, and size of current window
            max_count = max(max_count, right - left + 1 )
    
        return max_count