Variable Size Sliding Window Algorithm.

Sliding Window is an efficient approach to solve problems involving contiguous subarrays. It can be used to find the maximum or minimum sum of a contiguous subarray of size k. This approach involves maintaining a "window" that moves from the left to the right of the array, keeping track of the sum of the elements within the window.

Variable Size Sliding Window.

The Variable Size Sliding Window Algorithm, also known as Dynamic Sliding Window, is a technique used for efficiently processing arrays or lists to avoid unnecessary re-computation. Unlike the Fixed Size Sliding Window, where the window size remains constant, the Variable Size Sliding Window allows the window to dynamically adjust its size based on certain conditions.

Approach of Variable Size Sliding Window:

In this approach, we use two pointers left and right to define the window size. We move our right pointer to expand the window size until a certain condition is violated. Similarly, we move our left pointer to shrink the size of the window to the desired condition. Each time we either store a result or perform some computation whenever the size of the window is changed. We repeat these steps until the right pointer reaches the end of the array. 

Let's understand the working of the Variable Size Sliding Window Algorithm with an example problem.

Example to Illustrate the Dynamic Sliding Window Technique. 

Problem: Given an array of positive integer nums and a positive integer target, find the minimum length of a contiguous subarray whose sum is greater than or equal to the target. If no such subarray exists, return 0.

Example:

Input: num[] = {2, 3, 1, 2, 4, 3} target = 7
Output: 2

Explanation: The subarray [4,3] has the minimum length 
among the contiguous subarrays whose sum is greater than or equal to 7.

There are multiple approaches to solving this problem but here we will focus on the sliding window approach.

Algorithm:

Below are the steps to follow to solve this problem:

Step 1: We initialize a variable, 'minLen', to hold the minimum length of the contiguous subarray found so far. We also initialize a variable, 'sum', to keep track of the sum of the elements in the current window.

Step 2: We iterate over the input array, using a for loop to iterate through each element. For each element, we add its value to the 'sum' variable.

Step 3: Inside the for loop, we check if the 'sum' is greater than or equal to the target. If it is, we update the 'minLen' variable to be the minimum of its current value and the current window's length (calculated using the 'right' pointer).

Step 4: After updating the 'minLen' variable, we slide the window to the right by subtracting the first element of the current window from the 'sum' variable. This involves incrementing the 'left' pointer by 1.

Step 5: We repeat steps 3-4 until the 'right' pointer reaches the end of the input array.

Step 6: Finally, we return the value of the 'minLen' variable, which represents the minimum length of the contiguous subarray whose sum is greater than or equal to the target.

Below is the code implementation of the Variable size Sliding Window problem.

C++ Code:

// C++ code implementation of finding the minimum length 
//of the subarray for given sum
#include <iostream>
#include <vector>
#include <climits> 

using namespace std;

int minSubarrayLen(int target, vector<int>& nums) {
    int n = nums.size();
    int left = 0, right = 0;
    int minLen = INT_MAX;
    int sum = 0;

    while (right < n) {
        sum += nums[right];

        while (sum >= target) {
            minLen = min(minLen, right - left + 1);
            sum -= nums[left];
            left++;
        }

        right++;
    }

    return (minLen == INT_MAX) ? 0 : minLen;
}

int main() {
    vector<int> nums = {2, 3, 1, 2, 4, 3};
    int target = 7;
    cout << minSubarrayLen(target, nums) << endl; 
    return 0;
}

Output:

2

Java Code:

// Java code to find minimum length subarray 
// for the given target 
public class VariableSizeSlidingWindow {

    public static int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0, sum = 0;
        int minLength = Integer.MAX_VALUE;

        while (right < nums.length) {
            sum += nums[right];

            while (sum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                sum -= nums[left];
                left++;
            }

            right++;
        }

        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        int target = 7;

        int result = minSubArrayLen(target, nums);

        System.out.println("Minimum Length: " + result);
    }
}

Output:

Minimum Length: 2

• Time Complexity: The time complexity is O(n), where n is the length of the input array. This is because each element in the array is processed exactly once. 

• Space Complexity: The space complexity is O(1), as we only use a constant amount of space to store the necessary variables.

Binary Search Algorithm in Python.

There are two popular searching algorithms to find a target value in an Array 'Linear Search' and 'Binary Search'. In this article, we will learn about the Binary Search Algorithm in detail using Python Programming.

Binary Search Algorithm.

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. The only drawback of this search algorithm is that we need a sorted array to perform our search operation to find the target element in the given list. 

Below are the algorithm steps to follow:

Step 1: Set two pointers, low and high, to the start and end of the array, respectively.

Step 2: Loop until the base case is reached:

• Calculate the middle index as (low + high) // 2.

• If the element at the middle index is equal to the target, return the index.

• If the element is greater than the target, update high to mid - 1 and repeat the search in the left half.

• If the element is smaller than the target, update low to mid + 1 and repeat the search in the right half.

Step 3: If low is greater than high, the target is not present. Return -1.

Example of Binary Search:

Let's go through an example to understand the workings of the Binary Search Algorithm.

We have a sorted array [1, 3, 5, 7, 9, 11, 13, 15, 17, 19], and we want to find the index of element 13.

Initialize Pointers: Set low to 0 and high to 9 (the indices of the array's first and last elements).

Iteration 1:

• Calculate mid as (low + high) // 2 = (0 + 9) // 2 = 4.
• Compare arr[mid] (element at index 4) with the target (13).
• Since arr[4] is less than 13, update low to mid + 1, making low = 5.

Iteration 2:

• Calculate mid as (low + high) // 2 = (5 + 9) // 2 = 7.
• Compare arr[mid] (element at index 7) with the target (13).
• Since arr[7] is greater than 13, update high to mid-1, making high = 6.

Iteration 3:

• Calculate mid as (low + high) // 2 = (5+ 6) // 2 = 5.
• Compare arr[mid] (element at index 5) with the target (13).
• Since arr[5] is less than 13, update low to mid + 1, making low = 6.

Iteration 4:

• Calculate mid as (low + high) // 2 = (6 + 6) // 2 = 6.
• Compare arr[mid] (element at index 6) with the target (13).
• Since arr[6] is equal to 13, we found the target. Return the index 6.

The target element 13 is present at index 9 in the array.

Python Program for Binary Search Using Iteration.

# Python code for Iterative Binary Search to find
# target element from sorted array
def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        mid_element = arr[mid]

        if mid_element == target:
            return mid
        elif mid_element < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# Example
sorted_array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target_element = 6
result = binary_search(sorted_array, target_element)

if result != -1:
    print(f"Element {target_element} is present at index {result}.")
else:
    print(f"Element {target_element} is not present in the array.")

Output:

Element 6 is present at index 5.

• Time Complexity: The time complexity of binary search is O(log n), where 'n' is the number of elements in the array.

• Space Complexity: The space complexity is O(1), indicating that the memory used by the algorithm remains constant regardless of the input size.

Python Program for Binary Search Using Recursion.

# Python code for Recursive Binary Search Algorithm
def binary_search_recursive(arr, low, high, target):
    if low <= high:
        mid = (low + high) // 2

        # Check if the target is present at the middle
        if arr[mid] == target:
            return mid
        # If the target is smaller, search in the left half
        elif arr[mid] > target:
            return binary_search_recursive(arr, low, mid - 1, target)
        # If the target is larger, search in the right half
        else:
            return binary_search_recursive(arr, mid + 1, high, target)
    else:
        # Target is not present in the array
        return -1

# Example usage:
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 13
result = binary_search_recursive(arr, 0, len(arr) - 1, target)

if result != -1:
    print(f"Element {target} is present at index {result}.")
else:
    print(f"Element {target} is not present in the array.")

Output:

Element 13 is present at index 6.

The base case of the above recursive function is when low is greater than high, indicating that the search range is empty. The function will return the index at which the element is present else it will return -1 which means the target element is not present in the given array.

• Time Complexity: The time complexity is O(log n) because, at each step, the search range is divided by 2.

• Space Complexity: The space complexity is O(log n) due to the recursive call stack.

Linear Search Algorithm in Python.

Given an integer array arr[] of size n and an element x, the task is to write a Python program to search for the element x in the given array.

Example:

Input: arr = [12, 10, 9, 11, 41] x = 9
Output: X is present at index 2.

Input: arr = [1, 2, 3, 4, 6, 9] x = 7
Output: Not Found

Input: arr = [-1, 2, 4] x = 2
Output: X is present at index 1

There are two popular algorithms one is Linear Search and another is Binary Search for searching an element in an array. In this article, we are going to learn how to use the Linear Search algorithm in Python programming.

Linear Search Algorithm.

Linear search, also known as sequential search, is a straightforward searching algorithm where we start from the beginning of the array and compare each element with the target value until a match is found or the entire array has been traversed.

 

Below are the algorithm steps to do the linear search:

• Step 1: Start from the first element of the array.

• Step 2: Compare the current element with the target value x.

• Step 3: If the element is equal to the target x, return the index.

• Step 4: If not, move to the next element.

• Step 5: Repeat steps 2-4 until the target is found or the end of the array is reached.

• Step 6: If the target is not found after traversing the entire array, return -1.

Python Program for Linear Search.

Below is the Python code implementation of Linear search using an iterative method.

# Python code to search element using Linear Search
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Target found, return the index
    return -1  # Target not found

# Example usage
array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
target_value = 6
result = linear_search(array, target_value)

if result != -1:
    print(f'Target {target_value} found at index {result}.')
else:
    print(f'Target {target_value} not found in the array.')

Output:

Target 6 found at index 7.

• Time Complexity: The worst-case time complexity is O(n) when the target element is present at the end of the array. 

• Space Complexity: O(1) - Linear search is an "in-place" algorithm that doesn't require additional memory proportional to the input size.

Python Program for Linear Search Using Recursion.

In this recursive algorithm, we have two base cases: first, if the current element equals the target, it returns the current index; second, if the current index surpasses the array length, indicating the target is not present, it returns -1. 

In the recursive case, the function calls itself with an incremented index to continue the search in the remaining array. This process repeats until one of the base cases is met.

Below is the Python code implementation of Linear search using recursion.

Python Code.

# Python program to search element using Recursive Method
def linear_search(arr, target, current_index=0):
    # Base case: target found
    if current_index < len(arr):
        if arr[current_index] == target:
            return current_index
    
    # Base case: target not found
    if current_index == len(arr):
        return -1
    
    # Recursive case: search in the remaining array
    return linear_search_recursive(arr, target, current_index + 1)

# Example
arr = [1, 2, 3, 4, 5]
target = 3

result = linear_search(arr, target)

if result != -1:
    print(f"Target {target} found at index {result}.")
else:
    print(f"Target {target} not found in the array.")

Output:

Target 3 found at index 2.

• Time Complexity: Linear search has a time complexity of O(n) in the worst case.
• Space Complexity: The recursive calls use the call stack, and in the worst case, the space complexity is O(n) due to the depth of the recursion. 

Zeller's Congruence Algorithm in C.

Zeller's Congruence is an algorithm devised by Christian Zeller to calculate the day of the week for any date. The algorithm provides a simple and efficient way to determine the weekday for any date in the Gregorian calendar. 

The formula for Zeller's Congruence is given by:

Where:

• h is the day of the week (0 = Saturday, 1 = Sunday, 2 = Monday, ..., 6 = Friday)
• q is the day of the month
• m is the month (3 = March, 4 = April, ..., 14 = February)
• K is the year of the century (i.e., year mod 100)
• J is the zero-based century (actually ⌊ year/100 ⌋)

The result h corresponds to the days of the week, where 0 is Saturday, 1 is Sunday, and so on.

Here's a breakdown of the formula:

• The term $\lfloor \frac{13\cdot (�+1)}{5}\rfloor$ adjusts for the months (January and February are counted as months 13 and 14 of the previous year).
• $�+\lfloor \frac{�}{4}\rfloor$ takes care of the year part.
• $\lfloor \frac{�}{4}\rfloor -2\cdot �$ deals with the century adjustment.

Example: Let's calculate the day of the week for March 1, 2023.

After calculation, we got h value equal to 4 which means March 1, 2023, is Thursday.

C program Implementation of Zeller's Congruence.

// C program to find day of the week for a Date
// Zeller's Congruence
#include <stdio.h>

int zellersCongruence(int day, int month, int year) {
    if (month < 3) {
        month += 12;
        year--;
    }

    int K = year % 100;
    int J = year / 100;

    int h = (day + (13 * (month + 1)) / 5 + K + K / 4 + J / 4 - 2 * J) % 7;

    // Convert h to a more conventional form 
    // (0 = Saturday, 1 = Sunday, ..., 6 = Friday)
    return h % 7;
}

int main() {
    int day = 1, month = 3, year = 2023;

    int dayOfWeek = zellersCongruence(day, month, year);
    char arr[7][10] = {"Saturday", "Sunday", "Monday", 
                       "Tuesday", "Wednesday", "Thursday", "Friday"};
    
    printf("March 1, 2023 is a %s", arr[dayOfWeek]);
    
    return 0;
}

Output:

March 1, 2023 is a Wednesday

In this C program, the zellersCongruence function calculates the day of the week using Zeller's Congruence, and the result is then displayed in a user-friendly format.