# Array Algorithms

## Easy

### Rotate Array

Rotate the array A by B positions

```java
ArrayList<Integer> result = new ArrayList<Integer>();
  for (int i = 0; i < A.size(); i++) {
  result.add( A.get( (i + B) % A.size() ) );
}
```

### Swap to Equal Sum

We are given two arrays of integers. Our task is to **find a pair of values**, one from each array, that we can **swap** so that **both arrays have the same sum after the swap**.

Example

```
Array A = {4, 1, 2, 1, 1, 2}
Array B = {3, 6, 3, 3}
```

**Output**: `{1, 3}`\
This means: swap `1` from A and `3` from B → now the sums of both arrays will be equal.

Let:

* `sumA` = sum of array A
* `sumB` = sum of array B

After swapping a pair `a` (from A) and `b` (from B), the new sums would be:

* A's new sum: `sumA - a + b`
* B's new sum: `sumB - b + a`

We want both sums to be **equal**:

```
sumA - a + b = sumB - b + a
```

Simplify:

```
2(b - a) = sumB - sumA
```

So the required condition is:

```
b - a = (sumB - sumA) / 2
```

Let’s call that `delta = (sumB - sumA) / 2`

sumA = 4 + 1 + 2 + 1 + 1 + 2 = 11\
sumB = 3 + 6 + 3 + 3 = 15

delta = (15 - 11) / 2 = 2

We need to find a pair (a, b) such that b - a = 2\
So, iterate over A, and for each a, check if a + delta exists in B.

```java
import java.util.*;

public class SwapToEqualSum {

    public static int[] findSwapValues(int[] A, int[] B) {
        int sumA = Arrays.stream(A).sum();
        int sumB = Arrays.stream(B).sum();
        
        int delta = sumB - sumA;
        if (delta % 2 != 0) return null; // no solution if delta is odd
        delta /= 2;

        Set<Integer> setB = new HashSet<>();
        for (int b : B) setB.add(b);

        for (int a : A) {
            int target = a + delta;
            if (setB.contains(target)) {
                return new int[]{a, target};
            }
        }

        return null;
    }

    public static void main(String[] args) {
        int[] A = {4, 1, 2, 1, 1, 2};
        int[] B = {3, 6, 3, 3};

        int[] result = findSwapValues(A, B);
        if (result != null) {
            System.out.println("Swap: " + Arrays.toString(result));
        } else {
            System.out.println("No swap can equalize the arrays.");
        }
        // Swap: [1, 3]
    }
}
```

## Medium

### Maximum Subarray Sum

Given an array of integers (both positive and negative). Find the contiguous sequence with the largest sum. Return the sum.

Example

lnput: 2, -8, 3, -2, 4, -10

Output: 5 ( i. e • , { 3, -2, 4})

**Kadane’s Algorithm** is a famous and efficient algorithm used to solve the **"Maximum Subarray Problem"** that is, to find the contiguous subarray within a one-dimensional array of numbers which has the **largest sum**.

Idea is instead of checking every subarray, move through the array while tracking the maximum sum ending at the current index and updating the global maximum sum.

* Keep two variables:
  * `maxSoFar`: the global maximum sum found so far.
  * `currentMax`: the maximum subarray sum ending at the current position.
* At each index `i`, calculate:

  ```
  currentMax = max(array[i], currentMax + array[i])
  maxSoFar = max(maxSoFar, currentMax)
  ```
* If `currentMax` becomes less than the current element, start a new subarray.

Explanation

Given:\
`[2, -8, 3, -2, 4, -10]`

Start with:\
`currentMax = maxSoFar = 2`

Now go through the rest:

* `-8`: `currentMax = max(-8, 2 + (-8)) = -6`, `maxSoFar = max(2, -6) = 2`
* `3`: `currentMax = max(3, -6 + 3) = 3`, `maxSoFar = max(2, 3) = 3`
* `-2`: `currentMax = max(-2, 3 + (-2)) = 1`, `maxSoFar = 3`
* `4`: `currentMax = max(4, 1 + 4) = 5`, `maxSoFar = 5`
* `-10`: `currentMax = max(-10, 5 + (-10)) = -5`, `maxSoFar = 5`&#x20;

Final result:\
`maxSoFar = 5`&#x20;

<table data-header-hidden><thead><tr><th width="110.81512451171875"></th><th width="111.353271484375"></th><th></th><th></th></tr></thead><tbody><tr><td>Index</td><td>Element</td><td>Current Sum (<code>curSum</code>)</td><td>Max Sum (<code>maxSum</code>)</td></tr><tr><td>0</td><td>2</td><td>2</td><td>2</td></tr><tr><td>1</td><td>-8</td><td>-6</td><td>2</td></tr><tr><td>2</td><td>3</td><td>3</td><td>3</td></tr><tr><td>3</td><td>-2</td><td>1</td><td>3</td></tr><tr><td>4</td><td>4</td><td>5</td><td>5 </td></tr><tr><td>5</td><td>-10</td><td>-5</td><td>5</td></tr></tbody></table>

→ Max sum = **5**, subarray = `[3, -2, 4]`

```java
public static int[] maxSubArrayWithIndices(int[] arr) {
    int maxSum = Integer.MIN_VALUE, curSum = 0;
    int start = 0, end = 0, tempStart = 0;

    for (int i = 0; i < arr.length; i++) {
        curSum += arr[i];

        if (curSum > maxSum) {
            maxSum = curSum;
            start = tempStart;
            end = i;
        }

        if (curSum < 0) {
            curSum = 0;
            tempStart = i + 1;
        }
    }

    System.out.println("Subarray with max sum: " + Arrays.toString(Arrays.copyOfRange(arr, start, end + 1)));
    return new int[]{maxSum};
}
```

### Pairs of Sum

**Given:**

* An integer array `arr[]`
* An integer `targetSum`

**Task:**\
Find all **pairs** `(a, b)` such that `a + b == targetSum`.

#### **Approach 1: Brute Force (O(n²))**

Compare every pair:

```java
for (int i = 0; i < arr.length; i++) {
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] + arr[j] == targetSum) {
            // print pair
        }
    }
}
```

#### **Approach 2: Using HashSet (Optimal, O(n))**

```java
Input: arr = [1, 3, 2, 2, 4, 0, 5], targetSum = 4

Output: 
(1, 3)
(2, 2)
(4, 0)
```

```java
import java.util.*;

public class PairSum {
    public static void findPairs(int[] arr, int targetSum) {
        Set<Integer> seen = new HashSet<>();
        Set<String> printed = new HashSet<>(); // To avoid printing duplicates

        for (int num : arr) {
            int complement = targetSum - num;
            if (seen.contains(complement)) {
                // Ensure (a, b) and (b, a) are not printed separately
                int min = Math.min(num, complement);
                int max = Math.max(num, complement);
                String pair = min + "," + max;

                if (!printed.contains(pair)) {
                    System.out.println("(" + min + ", " + max + ")");
                    printed.add(pair);
                }
            }
            seen.add(num);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 2, 4, 0, 5};
        int targetSum = 4;
        findPairs(arr, targetSum);
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://www.pranaypourkar.co.in/the-programmers-guide/algorithm/array-algorithms.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.