Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Espaรฑol

โ€บProblems: Sorting & Searching

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

Merge Sorted Array

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

Note:

  • The number of elements initialized in nums1 and nums2 are m and n respectively.
  • You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

๐Ÿ‘‰ Link here to the repo to solve the problem

imagen

๐Ÿ‘Œ Tips

If you simply consider one element each at a time from the two arrays and make a decision and proceed accordingly, you will arrive at the optimal solution.

You can easily solve this problem if you simply think about two elements at a time rather than two arrays. We know that each of the individual arrays is sorted. What we don't know is how they will intertwine. Can we take a local decision and arrive at an optimal solution?

Try moving from the end of the array to the beginning.

๐Ÿ‘Š Solution 1

This is a simple, yet inefficient solution. This would take M to copy the array onto nums1, and the O(N Log N) to sort the whole array.

This can be improved, as we are not really taking advantage that the arrays are already sorted.

public void badMerge(int[] nums1, int m, int[] nums2, int n) {
    int length = nums1.length - 1;
    while (n > 0) { // copy elements to the end of the array
        nums1[length] = nums2[n - 1];
        length--;
        n--;
    }
    Arrays.sort(nums1);
}

๐Ÿ‘Š Solution 2

Typically, one could achieve O(n+m) time complexity in a sorted array(s) with the help of two pointers approach.

In order to do this, we start appending at the end of the first array. We need one pointer for each one of them, whoever is the biggest we will append at the end.

nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

we compare 6 with 3, 

6 > 3 ? add 6

nums1 = [1,2,3,0,0,6], m = 3
nums2 = [2,5,6],       n = 2

5 > 3 ? add 5

nums1 = [1,2,3,0,5,6], m = 3
nums2 = [2,5,6],       n = 1

2 > 3 ? add 3

nums1 = [1,2,3,3,5,6], m = 2
nums2 = [2,5,6],       n = 1

And so on...

The code in Java:

public void merge(int[] nums1, int m, int[] nums2, int n) {
    // two get pointers for nums1 and nums2
    int p1 = m - 1;
    int p2 = n - 1;
    // set pointer for nums1
    int p = m + n - 1;

    // while there are still elements to compare
    while ((p1 >= 0) && (p2 >= 0))
        // compare two elements from nums1 and nums2
        // and add the largest one in nums1
        nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];

    // add missing elements from nums2
    System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
}

Question borrowed from โ€œleetcode.comโ€

Last updated on 4/4/2020
โ† (Harder) Random NodeFirst Bad Version โ†’
  • ๐Ÿ‘‰ Link here to the repo to solve the problem
  • ๐Ÿ‘Œ Tips
  • ๐Ÿ‘Š Solution 1
  • ๐Ÿ‘Š Solution 2
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright ยฉ 2021 Kodr