Interview 150
Merge Sorted Array
- Problem
- LC 88
- File
- interview150_LC88MergeSortedArray.java
- Path
- pkg5leetcode/interview150/interview150_LC88MergeSortedArray.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC88MergeSortedArray.java
- Approach
- Fill from end comparing largest elements of both arrays.
- Complexity
- Time O(m+n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Merge Sorted Array | LC 885 * APPROACH: Fill from end comparing largest elements of both arrays.6 * COMPLEXITY: Time O(m+n), Space O(1)7 */8public class interview150_LC88MergeSortedArray {9 static void merge(int[] nums1, int m, int[] nums2, int n) {10 int i = m - 1, j = n - 1, k = m + n - 1;11 while (j >= 0) {12 if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--];13 else nums1[k--] = nums2[j--];14 }15 }16 17 public static void main(String[] args) {18 int[] a = {1, 2, 3, 0, 0, 0};19 merge(a, 3, new int[]{2, 5, 6}, 3);20 check(java.util.Arrays.equals(a, new int[]{1, 2, 2, 3, 5, 6}), "case1");21 int[] b = {1};22 merge(b, 1, new int[]{}, 0);23 check(java.util.Arrays.equals(b, new int[]{1}), "case2");24 System.out.println("all tests passed");25 }26 27 static void check(boolean cond, String name) {28 if (!cond) throw new AssertionError("FAILED: " + name);29 System.out.println(" PASS " + name);30 }31}