K Radius Subarray Averages

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        windowSize = 2 * k + 1
        ans = [-1] * n

        if n < windowSize:
            return ans

        prefixSum = [0] * (n + 1)
        for i in range(n):
            prefixSum[i + 1] = prefixSum[i] + nums[i]

        for i in range(k, n - k):
            ans[i] = (prefixSum[i + k + 1] - prefixSum[i - k]) // windowSize

        return ans

Identifying Problem Isomorphism

“K Radius Subarray Averages” can be mapped to “Moving Average from Data Stream”.

In the “Moving Average from Data Stream” problem, we are maintaining a moving window of size M and calculating the average of the numbers in this window as new elements get added to the stream. This concept is similar to calculating the k-radius average in the “K Radius Subarray Averages” problem, where k denotes the radius around a specific index.

The reason this is an approximate mapping is due to a few differences. In the “K Radius Subarray Averages” problem, we need to manage a varying window size when the index is close to the beginning or end of the array, and assign a value of -1 when there are fewer than k elements on either side. The “Moving Average from Data Stream” problem doesn’t have this requirement, as the window size is constant once it has filled up, and it doesn’t require us to deal with boundary conditions.

“Moving Average from Data Stream” is simpler, as it deals with a constant window size and doesn’t have the boundary condition handling. “K Radius Subarray Averages” problem requires us to handle these additional complexities.

10 Prerequisite LeetCode Problems

The problem can be solved using the sliding window approach, which is a common technique for array problems where a certain condition needs to be satisfied in a subarray or segment of the array. Here are some problems to understand and apply the sliding window technique:

  1. LeetCode 3: Longest Substring Without Repeating Characters Here you need to find the length of the longest substring without repeating characters, which can be solved using the sliding window approach.

  2. LeetCode 209: Minimum Size Subarray Sum The problem is about finding the minimal length of a contiguous subarray of which the sum is greater than or equal to a target number.

  3. LeetCode 567: Permutation in String This problem involves checking if a permutation of the first string exists in the second string, which can be solved using the sliding window technique.

  4. LeetCode 904: Fruit Into Baskets This problem involves finding the maximum number of fruits you can collect, which can be seen as a longest subarray problem that can be solved using the sliding window approach.

  5. LeetCode 1004: Max Consecutive Ones III Here you’re allowed to flip at most K zeroes to ones to find the longest subarray consisting of all ones.

  6. LeetCode 1052: Grumpy Bookstore Owner In this problem, you need to find the maximum number of customers that can be satisfied over a period of minutes, which involves a variant of the sliding window technique.

  7. LeetCode 424: Longest Repeating Character Replacement This problem involves replacing some characters to get the longest possible substring having all repeating letters.

  8. LeetCode 978: Longest Turbulent Subarray This problem involves finding a subarray where the comparison sign flips between each adjacent pair of numbers.

  9. LeetCode 485: Max Consecutive Ones This problem requires you to find the maximum number of consecutive 1s in a binary array, which can be solved with the sliding window technique.

  10. LeetCode 1438: Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit This problem involves finding the longest subarray such that the absolute difference between any two elements is less than or equal to the limit.

These cover various aspects and variations of the sliding window technique which will be beneficial to solve the given problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
  def getAverages(self, nums: List[int], k: int) -> List[int]:
    res = [-1]*len(nums)

    left, curWindowSum, diameter = 0, 0, 2*k+1
    for right in range(len(nums)):
      curWindowSum += nums[right]
      if (right-left+1 >= diameter):
        res[left+k] = curWindowSum//diameter
        curWindowSum -= nums[left]
        left += 1
    return res

You are given a 0-indexed array nums of n integers, and an integer k.

The k-radius average for a subarray of nums centered at some index i with the radius k is the average of all elements in nums between the indices i - k and i + k (inclusive). If there are less than k elements before or after the index i, then the k-radius average is -1.

Build and return an array avgs of length n where avgs[i] is the k-radius average for the subarray centered at index i.

The average of x elements is the sum of the x elements divided by x, using integer division. The integer division truncates toward zero, which means losing its fractional part.

For example, the average of four elements 2, 3, 1, and 5 is (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75, which truncates to 2.

Example 1:

Input: nums = [7,4,3,9,1,8,5,2,6], k = 3 Output: [-1,-1,-1,5,4,4,-1,-1,-1] Explanation:

  • avg[0], avg[1], and avg[2] are -1 because there are less than k elements before each index.
  • The sum of the subarray centered at index 3 with radius 3 is: 7 + 4 + 3 + 9 + 1 + 8 + 5 = 37. Using integer division, avg[3] = 37 / 7 = 5.
  • For the subarray centered at index 4, avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4.
  • For the subarray centered at index 5, avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4.
  • avg[6], avg[7], and avg[8] are -1 because there are less than k elements after each index. Example 2:

Input: nums = [100000], k = 0 Output: [100000] Explanation:

  • The sum of the subarray centered at index 0 with radius 0 is: 100000. avg[0] = 100000 / 1 = 100000. Example 3:

Input: nums = [8], k = 100000 Output: [-1] Explanation:

  • avg[0] is -1 because there are less than k elements before and after index 0.

Constraints:

n == nums.length 1 <= n <= 105 0 <= nums[i], k <= 105

Problem Classification

The “K Radius Subarray Averages” can be classified as a Running Calculation problem.

The problem statement implies a process of continually updating a calculation (in this case, an average) as you move through a sequence of numbers (which could represent anything - it doesn’t necessarily need to be an ‘array’ in the computer science sense). So, it falls into a category where you’re asked to keep a “running” or ongoing calculation.

Language Agnostic Coding Drills

  1. Basic Syntax and Structure: Familiarize yourself with basic coding structures like variable assignments, loops, and conditions. Understand how to define and use a function.

  2. Arrays/Lists: Understand the concept of arrays/lists, how to initialize them, how to iterate over them, and how to access elements by index.

  3. Arithmetic Operations: Get comfortable with basic mathematical operations: addition, subtraction, division, and multiplication.

  4. Understanding Classes and Methods: Learn how to define classes and methods. Get to know how self works in Python.

  5. Function Arguments: Understand the use of function arguments. Learn the difference between required and optional arguments, and how to set default values.

  6. Sliding Window Technique: This is a common algorithm design technique for array-based or list-based problems. It maintains a ‘window’ of elements and with each step, the window moves one element ahead (i.e., it ‘slides’).

  7. Complexity Analysis: Understand the time and space complexity of algorithms.

Problem-solving Approach: This code follows the sliding window approach. The problem is to find the average of all contiguous subarrays of size 2*k+1 in it.

  1. Initialize a result list with -1 values.

  2. The window size is 2*k+1, and the variables left and right are used to mark the start and end of the window.

  3. curWindowSum is used to calculate the sum of the elements in the current window.

  4. If the current window size is less than diameter, the window expands by moving the right pointer and adding the new element to curWindowSum.

  5. If the window size is equal to diameter, calculate the average of current window and put it into the middle of the window in the result list, then slide the window to the right by moving both left and right pointers and updating curWindowSum.

  6. Repeat step 4 and 5 until right reaches the end of the list.

  7. Return the result list, which contains the averages for each sliding window of the list.

Targeted Drills in Python

1. Basic Syntax and Structure:

This drill is to practice basic Python syntax and structures, including defining variables, loops, and if-conditions.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# Variable assignment
x = 10

# For loop
for i in range(5):
    print(i)

# If condition
if x > 5:
    print('x is greater than 5')

2. Arrays/Lists:

Understanding how to create, iterate and access list elements in Python.

1
2
3
4
5
6
7
8
9

# Initialize a list
nums = [1, 2, 3, 4, 5]

# Iterate over a list
for num in nums:
    print(num)

# Access elements by index
print(nums[0])  # prints 1

3. Arithmetic Operations:

Practice basic arithmetic operations.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# Define numbers
a = 10
b = 20

# Addition
print(a + b)

# Subtraction
print(a - b)

# Division
print(a / b)

# Multiplication
print(a * b)

4. Understanding Classes and Methods:

Learn to define and use classes and methods.

1
2
3
4
5
6
7
8
9

# Define a class
class MyClass:
    # Define a method
    def say_hello(self):
        print("Hello, world!")

# Use the class and method
my_instance = MyClass()
my_instance.say_hello()

5. Function Arguments:

Understand function arguments, optional arguments and default values.

1
2
3
4
5
6
7

# Define a function with arguments
def greet(name, greeting="Hello"):
    print(f"{greeting}, {name}!")

# Use the function
greet("Alice")  # Uses default greeting
greet("Bob", "Good morning")  # Custom greeting

6. Sliding Window Technique:

Understand the sliding window technique with a basic example: calculate the moving average of an array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def moving_average(nums, window_size):
    window_sum = sum(nums[:window_size])
    averages = [window_sum / window_size]

    for i in range(window_size, len(nums)):
        window_sum = window_sum - nums[i - window_size] + nums[i]
        averages.append(window_sum / window_size)
        
    return averages

print(moving_average([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 3))

7. Complexity Analysis:

Understanding the time complexity is not a concept that can be practiced through a coding drill, but rather by analyzing different algorithms and recognizing their time and space complexity. Consider reading about Big O notation and common complexity classes like O(1), O(n), O(n^2), O(log n), O(n log n), etc.