Advanced Array Algorithms
Advanced array algorithms build on the foundational manipulation techniques
and focus on solving complex problems with optimal efficiency. These algorithms
are commonly used in coding interviews and real-world applications.
1. Kadane's Algorithm (Maximum Subarray Sum)
This algorithm finds the maximum sum of a contiguous subarray in a given array,
with a time complexity of O(n).
Problem: Given an array arr, find the sum of the largest contiguous
subarray.
Algorithm:
1. Initialize max_current and max_global with the first element of the
array.
2. Iterate through the array, updating max_current as the maximum of
the current element and max_current + current element.
3. Update max_global if max_current is greater.
Example in Python:
def kadane(arr):
max_current = max_global = arr[0]
for i in range(1, len(arr)):
max_current = max(arr[i], max_current + arr[i])
if max_current > max_global:
max_global = max_current
return max_global
Example in JavaScript:
function kadane(arr) {
let maxCurrent = arr[0], maxGlobal = arr[0];
for (let i = 1; i < arr.length; i++) {
maxCurrent = Math.max(arr[i], maxCurrent + arr[i]);
if (maxCurrent > maxGlobal) {
, maxGlobal = maxCurrent;
}
}
return maxGlobal;
}
2. Sliding Window Technique
The sliding window technique is used to optimize algorithms that require working
with a subset of elements within a larger dataset. It reduces the time complexity
to O(n) for problems involving contiguous subarrays.
Problem: Find the maximum sum of any subarray of size k.
Algorithm:
1. Compute the sum of the first k elements as the initial window sum.
2. Slide the window one element at a time by subtracting the first
element of the previous window and adding the next element.
3. Update the maximum sum if the current window sum is greater.
Example in Python:
def max_sum_subarray(arr, k):
max_sum = current_sum = sum(arr[:k])
for i in range(k, len(arr)):
current_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, current_sum)
return max_sum
Example in JavaScript:
function maxSumSubarray(arr, k) {
let maxSum = 0, currentSum = 0;
for (let i = 0; i < k; i++) {
currentSum += arr[i];
}
maxSum = currentSum;
for (let i = k; i < arr.length; i++) {
Advanced array algorithms build on the foundational manipulation techniques
and focus on solving complex problems with optimal efficiency. These algorithms
are commonly used in coding interviews and real-world applications.
1. Kadane's Algorithm (Maximum Subarray Sum)
This algorithm finds the maximum sum of a contiguous subarray in a given array,
with a time complexity of O(n).
Problem: Given an array arr, find the sum of the largest contiguous
subarray.
Algorithm:
1. Initialize max_current and max_global with the first element of the
array.
2. Iterate through the array, updating max_current as the maximum of
the current element and max_current + current element.
3. Update max_global if max_current is greater.
Example in Python:
def kadane(arr):
max_current = max_global = arr[0]
for i in range(1, len(arr)):
max_current = max(arr[i], max_current + arr[i])
if max_current > max_global:
max_global = max_current
return max_global
Example in JavaScript:
function kadane(arr) {
let maxCurrent = arr[0], maxGlobal = arr[0];
for (let i = 1; i < arr.length; i++) {
maxCurrent = Math.max(arr[i], maxCurrent + arr[i]);
if (maxCurrent > maxGlobal) {
, maxGlobal = maxCurrent;
}
}
return maxGlobal;
}
2. Sliding Window Technique
The sliding window technique is used to optimize algorithms that require working
with a subset of elements within a larger dataset. It reduces the time complexity
to O(n) for problems involving contiguous subarrays.
Problem: Find the maximum sum of any subarray of size k.
Algorithm:
1. Compute the sum of the first k elements as the initial window sum.
2. Slide the window one element at a time by subtracting the first
element of the previous window and adding the next element.
3. Update the maximum sum if the current window sum is greater.
Example in Python:
def max_sum_subarray(arr, k):
max_sum = current_sum = sum(arr[:k])
for i in range(k, len(arr)):
current_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, current_sum)
return max_sum
Example in JavaScript:
function maxSumSubarray(arr, k) {
let maxSum = 0, currentSum = 0;
for (let i = 0; i < k; i++) {
currentSum += arr[i];
}
maxSum = currentSum;
for (let i = k; i < arr.length; i++) {
