Array Algorithms & Techniques

int linearSearch(int arr[], int n, int x)
{
    for (int i = 0; i < n; i++)
        if (arr[i] == x)
            return i; // Return index if found
    return -1; // Return -1 if not found
}

public static int linearSearch(int[] arr, int x) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1;
}

def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1
 
# Pythonic alternative
def linear_search_pythonic(arr, x):
    return arr.index(x) if x in arr else -1

int binarySearch(int arr[], int l, int r, int x)
{
    while (l <= r) {
        int m = l + (r - l) / 2;
 
        // Check if x is present at mid
        if (arr[m] == x)
            return m;
 
        // If x greater, ignore left half
        if (arr[m] < x)
            l = m + 1;
 
        // If x is smaller, ignore right half
        else
            r = m - 1;
    }
 
    // If we reach here, then element was not present
    return -1;
}

int binarySearch(int arr[], int x) {
    int l = 0, r = arr.length - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
 
        if (arr[m] == x)
            return m;
 
        if (arr[m] < x)
            l = m + 1;
 
        else
            r = m - 1;
    }
    return -1;
}

def binary_search(arr, x):
    left, right = 0, len(arr) - 1
 
    while left <= right:
        mid = left + (right - left) // 2
 
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
 
    return -1

// Find two numbers in a sorted array that add up to target
pair<int, int> twoSumSorted(int arr[], int n, int target) {
    int left = 0, right = n - 1;
 
    while (left < right) {
        int sum = arr[left] + arr[right];
 
        if (sum == target)
            return {left, right};
        else if (sum < target)
            left++;    // Need larger sum
        else
            right--;   // Need smaller sum
    }
 
    return {-1, -1};  // No pair found
}

def two_sum_sorted(arr, target):
    """Find two numbers in sorted array that add up to target."""
    left, right = 0, len(arr) - 1
 
    while left < right:
        current_sum = arr[left] + arr[right]
 
        if current_sum == target:
            return (left, right)
        elif current_sum < target:
            left += 1    # Need larger sum
        else:
            right -= 1   # Need smaller sum
 
    return (-1, -1)  # No pair found
 
# Example
arr = [1, 3, 4, 5, 7, 8]
print(two_sum_sorted(arr, 9))  # (0, 5) -> indices of 1 and 8

// Returns new length with duplicates removed
int removeDuplicates(int arr[], int n) {
    if (n == 0) return 0;
 
    int writeIdx = 1;  // Slow pointer (where to write next unique)
 
    for (int readIdx = 1; readIdx < n; readIdx++) {  // Fast pointer
        if (arr[readIdx] != arr[readIdx - 1]) {
            arr[writeIdx] = arr[readIdx];
            writeIdx++;
        }
    }
 
    return writeIdx;  // New length
}
// Input:  [1, 1, 2, 2, 3, 4, 4, 5]
// Output: [1, 2, 3, 4, 5, ...]  length = 5

def remove_duplicates(arr):
    """Remove duplicates from sorted array in-place. Returns new length."""
    if not arr:
        return 0
 
    write_idx = 1  # Slow pointer
 
    for read_idx in range(1, len(arr)):  # Fast pointer
        if arr[read_idx] != arr[read_idx - 1]:
            arr[write_idx] = arr[read_idx]
            write_idx += 1
 
    return write_idx
 
arr = [1, 1, 2, 2, 3, 4, 4, 5]
new_len = remove_duplicates(arr)
print(arr[:new_len])  # [1, 2, 3, 4, 5]

int maxSumSubarray(int arr[], int n, int k) {
    // Compute sum of first window
    int windowSum = 0;
    for (int i = 0; i < k; i++)
        windowSum += arr[i];
 
    int maxSum = windowSum;
 
    // Slide the window: add next element, remove first element
    for (int i = k; i < n; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = max(maxSum, windowSum);
    }
 
    return maxSum;
}
 
// arr = {2, 1, 5, 1, 3, 2}, k = 3
// Windows: [2,1,5]=8, [1,5,1]=7, [5,1,3]=9, [1,3,2]=6
// Answer: 9

def max_sum_subarray(arr, k):
    """Find maximum sum of any subarray of size k."""
    n = len(arr)
    if n < k:
        return -1
 
    # Sum of first window
    window_sum = sum(arr[:k])
    max_sum = window_sum
 
    # Slide the window
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
 
    return max_sum
 
arr = [2, 1, 5, 1, 3, 2]
print(max_sum_subarray(arr, 3))  # 9