LeetCode Problems

Problem: Find First and Last Position of Element in Sorted Array

Given an array of integers numbers sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Problem statement taken from: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array

Example 1:

Input: nums = [5, 7, 7, 8, 8, 10], target = 8
Output: [3, 4]

Example 2:

Input: nums = [5, 7, 7, 8, 8, 10], target = 6
Output: [-1, -1]

Example 3:

Input: nums = [], target = 0
Output: [-1, -1]

Explanation

Brute force

The brute force approach will be to do a linear scan of the array. We use two pointers leftIndex and rightIndex start with the first array element.

When the first occurrence of the target element is found, we assign that index to leftIndex variable. We keep on iterating till the element is different from target. We assign the current index — 1 value to rightIndex.

Binary search solution

An efficient solution to this problem is to use binary search. Let’s check the algorithm below:

- set i = 0, j = nums.size() - 1
- set leftIndex and rightIndex to -1
- loop while i <= j
  - set mid = i + (j - i)/2
  - if nums[mid] > target
    - set j = mid - 1
  - else if nums[mid] < target
    - set i = mid + 1
  - else
    - leftIndex = mid
    - set j = mid - 1
- set i = 0, j = nums.size() - 1
- loop while i <= j
  - set mid = i + (j - i)/2
  - if nums[mid] > target
    - set j = mid - 1
  - else if nums[mid] < target
    - set i = mid + 1
  - else
    - rightIndex = mid
    - set i = mid + 1
- return [leftIndex, rightIndex]

The time complexity of the above approach is O(log(N)) and, space complexity is O(1).

Solution

var searchRange = function(nums, target) {
    let i = 0, j = nums.length - 1, mid;
    let leftIndex = -1, rightIndex = -1;
    while(i <= j){
        mid = ~~(i + (j - i) / 2);
        if(nums[mid] > target){
            j = mid - 1;
        } else if (nums[mid] < target){
            i = mid + 1;
        } else {
            leftIndex = mid;
            j = mid - 1;
        }
    }
    i = 0;
    j = nums.length - 1;
    while(i <= j){
        mid = ~~(i + (j - i) / 2);
        if(nums[mid] > target){
            j = mid - 1;
        } else if (nums[mid] < target){
            i = mid + 1;
        } else {
            rightIndex = mid;
            i = mid + 1;
        }
    }
    return [leftIndex, rightIndex];
};

Valid Parentheses Problem

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Problem statement taken from: https://leetcode.com/problems/valid-parentheses

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

Input: s = "{[]}"
Output: true

Explanation

The problem can be solved by using a stack or by recursion. For a large string, building up a stack of recursive calls consumes memory temporarily and may take more space than an iterative solution.

Stack

- initialize stack st and i = 0.- return true if the string is empty.- Loop while i < 0
  - if s[i] == '(' || s[i] == '[' || s[i] == '{'    // push the char to stack
    - st.push(s[i])  - else if s[i] == ')' && !st.empty() && st.top() == '(' ||
            s[i] == '}' && !st.empty() && st.top() == '{' ||
            s[i] == ']' && !st.empty() && st.top() == '['    // pop the top element if the current char is a closing brace provided
    // stack is not empty.
    - st.pop()  - else    // the string is not a valid parenthesis
    - return false  i++- return true if st.empty()- return false.

Solution

var isValid = function(s) {
   let st = [];
   const legend = {
     '(': ')',
     '{': '}',
     '[': ']'
   };   for (let i = 0; i < s.length; i++) {
     if (s[i] === '(' || s[i] === '{' || s[i] === '[') {
       st.push(s[i]);
     } else if (legend[st.pop()] !== s[i]) {
       return false;
     }
   }   return st.length ? 0 : 1;
};

Merge Two Sorted Array Problem

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.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

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.

Problem statement taken from: https://leetcode.com/problems/merge-sorted-array

Example 1:

Input: nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
Output: [1, 2, 2, 3, 5, 6]
Explanation: The arrays we are merging are [1, 2, 3] and [2, 5, 6].
The result of the merge is [1, 2, 2, 3, 5, 6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
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.

Explanation

The brute-force approach for the problem is to create a new array nums3 and keep adding elements from the two sorted arrays. Once all the elements from nums1 and nums2 are added to nums3 we copy back nums3 to nums1.

But the above solution will take an extra space of O(m + n). We need to sort the elements without any extra space.

The idea is to iterate both the arrays from right to left and keeping adding the elements to nums1 from right.

Let’s check the algorithm below:

- set i = m - 1, j = n - 1, k = m + n - 1
- loop for i >= 0 && j >= 0
  - if nums1[i] > nums2[j]
    - set nums1[k] = nums1[i--]
  - else
    - set nums1[k] = nums2[j--]
- loop while i >= 0
  - set nums1[k--] = nums1[i--]
- loop while j >= 0
  - set nums1[k--] = nums2[j--]

Solution

var merge = function(nums1, m, nums2, n) {
    let i, j, k;
    for(i = m - 1, j = n - 1, k = m + n - 1; i >= 0 && j >= 0; k--){
        if(nums1[i] >= nums2[j]){
            nums1[k] = nums1[i--];
        } else {
            nums1[k] = nums2[j--];
        }
    }
    while(i >= 0) {
        nums1[k--] = nums1[i--];
    }
    while(j >= 0) {
        nums1[k--] = nums2[j--];
    }
};