10000 P-88-merge-sorted-array · aditya-2k23/Leetcode@a65523b · GitHub
[go: up one dir, main page]
Skip to content

Commit a65523b

Browse files
aditya-2k23aditya-2k23
committed
P-88-merge-sorted-array
Implements solutions for LeetCode Problem 88: Merge Sorted Array, including both brute force and optimal two-pointer approaches. Adds a comprehensive README detailing problem description, examples, constraints, and solution strategies. Introduces test cases to validate both approaches across various scenarios, ensuring correctness and edge case handling.
1 parent 9e0450c commit a65523b

File tree

4 files changed

+237
-2
lines changed

4 files changed

+237
-2
lines changed

‎README.md

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
[![GitHub](https://img.shields.io/badge/Repository-blue?logo=github)](https://github.com/aditya-2k23/leetcode)
44
[![License](https://img.shields.io/badge/LICENSE-MIT-yellow?logo=license.svg)](https://github.com/aditya-2k23/leetcode/blob/main/LICENSE)
5-
![Problems Solved](https://img.shields.io/badge/Solved-10-brightgreen) <!-- Update this count as you solve more problems -->
5+
![Problems Solved](https://img.shields.io/badge/Solved-11-brightgreen) <!-- Update this count as you solve more problems -->
66
![Language](https://img.shields.io/badge/Language-Python%20%7C%20Java%20%7C%20C++-orange)
77
[![Wiki](https://img.shields.io/badge/Wiki-Available-blueviolet)](https://github.com/aditya-2k23/leetcode/wiki)
88
[![Discussions](https://img.shields.io/badge/Discussions-Open-blue)](https://github.com/aditya-2k23/leetcode/discussions)
@@ -29,6 +29,7 @@ Below is a list of problems solved in this repository:
2929
- [Problem 26: Remove Duplicates from Sorted Array](problems/P-26-remove-duplicates-from-sorted-array)
3030
- [Problem 27: Remove Element](problems/P-27-remove-element)
3131
- [Problem 35: Search Insert Position](problems/P-35-search-insert-position)
32+
- [Problem 88: Merge Sorted Array](problems/P-88-merge-sorted-array)
3233
- _(Add more problems as they are solved)_
3334

3435
## Purpose
@@ -97,4 +98,4 @@ This project is licensed under the MIT License. See the [LICENSE](LICENSE) file
9798

9899
Happy coding! 🚀
99100

100-
> _Last updated: June 3, 2025_
101+
> _Last updated: June 6, 2025_

‎problems/P-88-merge-sorted-array/README.md

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
# Problem 88: Merge Sorted Array
2+
3+
- **Difficulty**: Easy
4+
- **Topics**: Array, Two Pointers, Sorting
5+
- **LeetCode Link**: [Problem URL](https://leetcode.com/problems/merge-sorted-array/)
6+
7+
## Problem Description
8+
9+
You are given two integer arrays `nums1` and `nums2`, sorted in **non-decreasing order**, and two integers `m` and `n`, representing the number of elements in `nums1` and `nums2` respectively.
10+
11+
Merge `nums1` and `nums2` into a single array sorted in **non-decreasing order**.
12+
13+
The final sorted array should not be returned by the function, but instead be stored inside the array `nums1`. To accommodate this, `nums1` has a length of `m + n`, where the first `m` elements denote the elements that should be merged, and the last `n` elements are set to `0` and should be ignored. `nums2` has a length of `n`.
14+
15+
**Example 1:**
16+
17+
> **Input:** `nums1` = `[1,2,3,0,0,0]`, `m` = `3`, `nums2` = `[2,5,6]`, `n` = `3`
18+
> **Output:** `[1,2,2,3,5,6]`
19+
> **Explanation:** The arrays we are merging are `[1,2,3]` and `[2,5,6]`.
20+
> The result of the merge is `[1,2,2,3,5,6]` with the underlined elements coming from `nums1`.
21+
22+
**Example 2:**
23+
24+
> **Input:** `nums1` = `[1]`, `m` = `1`, `nums2` = `[]`, `n` = `0`
25+
> **Output:** `[1]`
26+
> **Explanation:** The arrays we are merging are `[1]` and `[]`.
27+
> The result of the merge is `[1]`.
28+
29+
**Example 3:**
30+
31+
> **Input:** `nums1` = `[0]`, `m` = `0`, `nums2` = `[1]`, `n` = `1`
32+
> **Output:** `[1]`
33+
> **Explanation:** The arrays we are merging are `[]` and `[1]`.
34+
> The result of the merge is `[1]`.
35+
> Note that because `m` = `0`, there are no elements in `nums1`. The `0` is only there to ensure the merge result can fit in `nums1`.
36+
37+
**Constraints:**
38+
39+
- `nums1.length == m + n`
40+
- `nums2.length == n`
41+
- `0 <= m, n <= 200`
42+
- `1 <= m + n <= 200`
43+
- `-10⁹ <= nums1[i], nums2[j] <= 10⁹`
44+
45+
**Follow up:** Can you come up with an algorithm that runs in `O(m + n)` time?
46+
47+
## Approach
48+
49+
### Brute Force Approach
50+
51+
1. Push all the elements of `nums2` into `nums1`.
52+
2. Remove all the zeroes from `nums1`.
53+
3. Sort `nums1`.
54+
55+
#### Complexity Analysis
56+
57+
- **Time Complexity**: `O(N(M + N))` due to the sorting step.
58+
- **Space Complexity**: `O(1)` if we ignore the space used by the sorting algorithm.
59+
60+
### Two Pointers Approach
61+
62+
1. Initialize two pointers, `i` for `nums1` and `j` for `nums2`, starting from the end of the valid elements in both arrays.
63+
2. Start filling `nums1` from the end, comparing the elements pointed by `i` and `j`.
64+
3. If `nums1[i]` is greater than `nums2[j]`, place `nums1[i]` at the end of `nums1` and decrement `i`.
65+
4. Otherwise, place `nums2[j]` at the end of `nums1` and decrement `j`.
66+
5. Continue this until all elements from `nums2` are merged into `nums1`.
67+
6. If there are any remaining elements in `nums2`, copy them to the beginning of `nums1`.
68+
69+
#### Complexity Analysis
70+
71+
- **Time Complexity**: `O(m + n)`
72+
- **Space Complexity**: `O(1)`
73+
74+
## Solution
75+
76+
- **Language**: _(e.g., Python, Java, C++)_
77+
- **File**: [solution.cpp](solution.cpp)
78+
79+
## Notes
80+
81+
- The brute force approach is straightforward but inefficient for larger inputs due to the sorting step.
82+
- The two pointers approach is optimal and does not require additional space, making it efficient for merging sorted arrays.
83+
84+
## Test Cases
85+
86+
See the [`./tests/`](./tests/) folder for example test cases.
87+
88+
### Running Tests
89+
90+
- **C++ (Simple)**: `cd tests; g++ test.cpp ../solution.cpp -o test; ./test`
91+
- **Python**: `cd tests; python test.py`
92+
- **Java**: `javac .\solution.java tests/test.java; java -cp ".;tests" test`
93+
94+
---
95+
96+
> **Solved on**: 06/06/2025 |
97+
> **Time taken**: 00:12:27 |
98+
> **Attempts**: 2

‎problems/P-88-merge-sorted-array/solution.cpp

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/*
2+
* LeetCode Problem: 88: Merge Sorted Array
3+
* Difficulty: Easy
4+
* Topics: Array, Two Pointers, Sorting
5+
* Date Solved: 06/06/2025
6+
*/
7+
8+
#include <bits/stdc++.h>
9+
using namespace std;
10+
11+
class Solution {
12+
public:
13+
// Brute Force Approach
14+
void BruteMerge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
15+
for (int i : nums2)
16+
nums1.push_back(i);
17+
18+
for (int i = 0; i < n; i++)
19+
nums1.erase(find(nums1.begin(), nums1.end(), 0));
20+
21+
sort(nums1.begin(), nums1.end());
22+
}
23+
24+
// Two Pointers Approach
25+
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
26+
int i = m - 1;
27+
int j = n - 1;
28+
int k = m + n - 1;
29+
30+
while (i >= 0 && j >= 0) {
31+
if (nums1[i] > nums2[j])
32+
nums1[k--] = nums1[i--];
33+
else
34+
nums1[k--] = nums2[j--];
35+
}
36+
37+
while (j >= 0)
38+
nums1[k--] = nums2[j--];
39+
}
40+
};

‎problems/P-88-merge-sorted-array/tests/test.cpp

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
#include "../solution.cpp"
2+
#include <bits/stdc++.h>
3+
using namespace std;
4+
5+
void printVector(const vector<int>& v) {
6+
cout << "[";
7+
for (size_t i = 0; i < v.size(); ++i) {
8+
cout << v[i];
9+
if (i + 1 < v.size()) cout << ",";
10+
}
11+
cout << "]";
12+
}
13+
14+
bool testBruteMerge(vector<int> nums1, int m, vector<int> nums2, int n, const vector<int>& expected, int testNumber) {
15+
Solution sol;
16+
vector<int> nums1_copy = nums1;
17+
sol.BruteMerge(nums1_copy, m, nums2, n);
18+
cout << "BruteMerge Test " << testNumber << ": ";
19+
if (nums1_copy == expected) {
20+
cout << "Passed ";
21+
printVector(nums1_copy);
22+
cout << endl;
23+
return true;
24+
}
25+
else {
26+
cout << "Failed. Expected ";
27+
printVector(expected);
28+
cout << ", Got ";
29+
printVector(nums1_copy);
30+
cout << endl;
31+
return false;
32+
}
33+
}
34+
35+
bool testMerge(vector<int> nums1, int m, vector<int> nums2, int n, const vector<int>& expected, int testNumber) {
36+
Solution sol;
37+
vector<int> nums1_copy = nums1;
38+
sol.merge(nums1_copy, m, nums2, n);
39+
cout << "merge Test " << testNumber << ": ";
40+
if (nums1_copy == expected) {
41+
cout << "Passed ";
42+
printVector(nums1_copy);
43+
cout << endl;
44+
return true;
45+
}
46+
else {
47+
cout << "Failed. Expected ";
48+
printVector(expected);
49+
cout << ", Got ";
50+
printVector(nums1_copy);
51+
cout << endl;
52+
return false;
53+
}
54+
}
55+
56+
void runTests() {
57+
int passed = 0, total = 0;
58+
// Test case 1
59+
vector<int> nums1a = { 1,2,3,0,0,0 };
60+
vector<int> nums2a = { 2,5,6 };
61+
vector<int> expected1 = { 1,2,2,3,5,6 };
62+
if (testBruteMerge(nums1a, 3, nums2a, 3, expected1, ++total)) passed++;
63+
if (testMerge(nums1a, 3, nums2a, 3, expected1, ++total)) passed++;
64+
// Test case 2
65+
vector<int> nums1b = { 1 };
66+
vector<int> nums2b = {};
67+
vector<int> expected2 = { 1 };
68+
if (testBruteMerge(nums1b, 1, nums2b, 0, expected2, ++total)) passed++;
69+
if (testMerge(nums1b, 1, nums2b, 0, expected2, ++total)) passed++;
70+
// Test case 3
71+
vector<int> nums1c = { 0 };
72+
vector<int> nums2c = { 1 };
73+
vector<int> expected3 = { 1 };
74+
if (testBruteMerge(nums1c, 0, nums2c, 1, expected3, ++total)) passed++;
75+
if (testMerge(nums1c, 0, nums2c, 1, expected3, ++total)) passed++;
76+
// Test case 4 (all zeros)
77+
vector<int> nums1d = { 0,0,0 };
78+
vector<int> nums2d = { 0,0,0 };
79+
vector<int> expected4 = { 0,0,0 };
80+
if (testBruteMerge(nums1d, 0, nums2d, 3, expected4, ++total)) passed++;
81+
if (testMerge(nums1d, 0, nums2d, 3, expected4, ++total)) passed++;
82+
// Test case 5 (negative numbers)
83+
vector<int> nums1e = { -1,0,0,0 };
84+
vector<int> nums2e = { -4,-3,-2 };
85+
vector<int> expected5 = { -4,-3,-2,-1 };
86+
if (testBruteMerge(nums1e, 1, nums2e, 3, expected5, ++total)) passed++;
87+
if (testMerge(nums1e, 1, nums2e, 3, expected5, ++total)) passed++;
88+
cout << "\nTest Results: " << passed << "/" << total << " passed.\n";
89+
if (passed == total) cout << "All tests passed!\n";
90+
else cout << "Some tests failed.\n";
91+
}
92+
93+
int main() {
94+
runTests();
95+
return 0;
96+
}

0 commit comments

Comments
 (0)
0