Arrays - Class 3

Lecture 45 :- Arrays - Class 3

In continuation of Arrays - Class 3, let's explore more advanced topics related to arrays.

1. Subarray: A subarray is a contiguous subset of elements from an array. Subarray problems involve finding or manipulating contiguous segments of an array.

Example - Maximum Subarray Sum: Given an array of integers, find the contiguous subarray with the largest sum.

cppCopy code

#include <iostream> #include <vector> int maxSubarraySum(std::vector<int>& nums) {    int maxSum = nums[0];    int currentSum = nums[0];    for (int i = 1; i < nums.size(); i++) {        currentSum = std::max(nums[i], currentSum + nums[i]);        maxSum = std::max(maxSum, currentSum);    }    return maxSum; } int main() {    std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};    int result = maxSubarraySum(nums);    std::cout << "Maximum subarray sum: " << result << std::endl;    return 0; }

1. Sliding Window Technique: The sliding window technique is used to solve problems involving subarrays or sublists. It involves using two pointers to create a window (a subarray) and sliding the window through the array to find the desired result. The sliding window size can be fixed or variable.

Example - Maximum Sum Subarray of Size K: Given an array of integers and a positive integer K, find the maximum sum of any contiguous subarray of size K.

cppCopy code

#include <iostream> #include <vector> int maxSumSubarrayOfSizeK(std::vector<int>& nums, int k) {    int maxSum = 0;    int currentSum = 0;    for (int i = 0; i < k; i++) {        currentSum += nums[i];    }    maxSum = currentSum;    for (int i = k; i < nums.size(); i++) {        currentSum += nums[i] - nums[i - k];        maxSum = std::max(maxSum, currentSum);    }    return maxSum; } int main() {    std::vector<int> nums = {2, 1, 5, 1, 3, 2};    int k = 3;    int result = maxSumSubarrayOfSizeK(nums, k);    std::cout << "Maximum sum of subarray of size " << k << ": " << result << std::endl;    return 0; }

1. Prefix Sum: Prefix sum is a technique used to efficiently calculate the sum of elements in a range of an array. It involves creating an auxiliary array where each element represents the sum of elements up to that position in the original array.

Example - Range Sum Query: Given an array of integers, preprocess it to efficiently answer queries for the sum of elements in a given range.

cppCopy code

#include <iostream> #include <vector> std::vector<int> calculatePrefixSum(std::vector<int>& nums) {    std::vector<int> prefixSum(nums.size());    prefixSum[0] = nums[0];    for (int i = 1; i < nums.size(); i++) {        prefixSum[i] = prefixSum[i - 1] + nums[i];    }    return prefixSum; } int rangeSumQuery(std::vector<int>& prefixSum, int left, int right) {    if (left == 0) {        return prefixSum[right];    } else {        return prefixSum[right] - prefixSum[left - 1];    } } int main() {    std::vector<int> nums = {1, 2, 3, 4, 5};    std::vector<int> prefixSum = calculatePrefixSum(nums);    int left = 1;    int right = 3;    int result = rangeSumQuery(prefixSum, left, right);    std::cout << "Sum of elements from index " << left << " to " << right << ": " << result << std::endl;    return 0; }

Arrays are a versatile data structure with many applications in programming and algorithms. Understanding advanced array techniques like subarrays, sliding window, and prefix sum can help you tackle a wide range of array-related problems more efficiently.