# Merge Two Sorted Arrays

## Question

> Merge two given sorted integer array A and B into a new sorted integer array.

## Example

```
Input: A = [1,2,3,4], B=[2,4,5,6]
Return: [1,2,2,3,4,4,5,6]
```

## Analysis

Two ways to think about this. Two pointers (one for each) for two input arrays until you reach the end for both of them. Or one pointer for the result array, and keep filling it until it's full. (more do the same distance first then fill in the rest).

Do both methods then compare them.

## Easy To Get Bug

```java
public int[] mergeSortedArray(int[] A, int[] B) {
    int[] R = new int[A.length + B.length]; //result
    int x = 0, y = 0;

    while (x + y < R.length) {
        if (y >= B.length || (x < A.length && A[x] <= B[y])) {
            R[x+y] = A[x++];
        } else {
            R[x+y] = B[y++];
        }
    }

    return R;
}
```

Keep filling then handle the case where n > m or n < m will be easier to write bug free code.

## Hard to Get Bug

```java
public int[] mergeSortedArray(int[] A, int[] B) {
    if (A == null || B == null)
        return null;
    int[] results = new int[A.length+B.length];
    // merge A and B until one array is exhausted
    int i = 0, ap = 0, bp = 0;
    while (ap < A.length && bp < B.length) {
        if (A[ap] < B[bp]) {
            results[i++] = A[ap++];
        } else {
            results[i++] = B[bp++];
        }
    }
    // if A has leftover elements
    while (ap < A.length) {
        results[i++] = A[ap++];
    }
    // else if B has leftover elements
    while (bp < B.length) {
        results[i++] = B[bp++];
    }
    return results;
}
```

## Merge Sorted Array ([LC.88](https://leetcode.com/problems/merge-sorted-array/))

> Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

nums1 has m elements and nums2 has n elements. Assume nums1 can hold m+n elements.

## Example

```
I: nums1 = [1, 2, 3, empty, empty], nums2 = [4, 5]
O: nums1 = [1, 2, 3, 4, 5]
I: nums1 = [1, 2, 3, 4, 0, 0, 0, 0], nums2 = [2, 4, 5, 6]
O: nums1 = [1, 2, 2, 3, 4, 4, 5, 6] // trace this left to right
I: nums1 = [1, 2, 3, 4, 0, 0, 0, 0], nums2 = [2, 4, 5, 6]
O: nums1 = [1, 2, 2, 3, 4, 4, 5, 6] // trace this right to left
```

## Analysis

So this problem is engineered so we can do it "in-place". The brute force solution will be O(n^2) compare it then shift if necessary. Where to merge? Can we do it in one pass? Maybe we can hold a temp variable? Well check out the solution after no clue for 2 min.

ᶘ ᵒᴥᵒᶅ By default our mind is always telling us to start from left -> right or small -> large. What if we start filling from large -> small? ohhhh

## Code

```java
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int tail = n + m - 1;
    int p1 = m - 1, p2 = n - 1;
    while (p1 >= 0 && p2 >= 0) {
        if (nums2[p2] >= nums1[p1]) {
            nums1[tail--] = nums2[p2--];
        } else {
            nums1[tail--] = nums1[p1--];
        }
    }
    // if m is bigger, we don't have to do anything b/c nums1 is sorted
    // if n is bigger
    while (p2 >= 0) {
        nums1[tail--] = nums2[p2--];
    }
}
```

## Recap

I can feel a significant improvement by writing analysis and going through thought process. I am no longer the no-clue-run-code-bug Zed, but the new pseudo-code-test-pass Zed. Congrats on understanding (read carefully and do examples) and figuring out (what paradigm / property to use) a problem. That's only the initial step. You also have to write a easy to follow pseudo code and write clear code then review and test a complex case.


---

# 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://zedive.gitbook.io/project-l/part-1/basic_data_structure/array_and_string/two-pointers/p1p2-pointers/merge-two-sorted-arrays.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.