Forem: Alkesh Ghorpade

Max Sum of Rectangle No Larger Than K

Alkesh Ghorpade — Thu, 29 Jun 2023 11:18:38 +0000

Problem statement

Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.

It is guaranteed that there will be a rectangle with a sum no larger than k.

Problem statement taken from: https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k.

Example 1:

Input: matrix = [[1, 0, 1], [0, -2, 3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

Example 2:

Input: matrix = [[2, 2, -1]], k = 3
Output: 3

Constraints:

- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -100 <= matrix[i][j] <= 100
- -10^5 <= k <= 10^5

Follow up: What if the number of rows is much larger than the number of columns?

Solution

Approach 1: Brute force

The naive approach is to check all the possible submatrices from the input matrix to compute the max sum of rectangles no larger than K. For each submatrix, we check if the sum of its elements is less than or equal to k or not. We store the sum of the submatrix no larger than k and return the answer.

A C++ solution of this approach is as follows:

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();
        int n = matrix[0].size();
        int result = numeric_limits<int>::min();

        vector<vector<vector<vector<int>>>> computeSum(
            m,
            vector<vector<vector<int>>>(
                n,
                vector<vector<int>>(
                    m,
                    vector<int>(n, 0)
                )
            )
        );

        for (int rowLength = 0; rowLength < m; ++ rowLength) {
            for (int columnLength = 0; columnLength < n; ++columnLength) {
                for (int i = 0; i + rowLength < m; ++i) {
                    for (int j = 0; j + columnLength < n; ++j) {
                        if (rowLength == 0 && columnLength == 0) {
                            computeSum[i][j][i + rowLength][j + columnLength] =
                                matrix[i][j];
                        } else if (rowLength == 0) {
                            computeSum[i][j][i + rowLength][j + columnLength] =
                                computeSum[i][j][i + rowLength][j + columnLength - 1]
                                +
                                matrix[i + rowLength][j + columnLength];
                        } else if (columnLength == 0) {
                            computeSum[i][j][i + rowLength][j + columnLength] =
                                computeSum[i][j][i + rowLength - 1][j + columnLength]
                                +
                                matrix[i + rowLength][j + columnLength];
                        } else {
                            computeSum[i][j][i + rowLength][j + columnLength] =
                                computeSum[i][j][i + rowLength - 1][j + columnLength]
                                +
                                computeSum[i][j][i + rowLength][j + columnLength - 1]
                                -
                                computeSum[i][j][i + rowLength - 1][j + columnLength - 1]
                                +
                                matrix[i + rowLength][j + columnLength];
                        }

                        if (computeSum[i][j][i + rowLength][j + columnLength] == k) {
                            return k;
                        } else if (computeSum[i][j][i + rowLength][j + columnLength] < k) {
                            result = max(
                                result,
                                computeSum[i][j][i + rowLength][j + columnLength]
                            );
                        }
                    }
                }
            }
        }

        return result;
    }
};

The time complexity of this approach is O(n ^ 4). The solution will time out for a huge matrix, which is not the optimal way.

Approach 2: Kanade algorithm

We can optimize the brute force approach by using the concept of the Kanade algorithm. Kadane’s algorithm finds a maximum sum contiguous subarray for a one-dimensional array in O(n) time. Using this concept, we will create an integer array that stores each row's prefix sums from column i to j where 0 < i < j < m. We will run Kadane’s algorithm on each such array to get the maximum possible sum closest to k of any subarray in the same way as we did in approach 1.

Please refer to this post Maximum Subarray for understanding the Kanade algorithm.

Let's check the algorithm.

Algorithm

// maxSumSubmatrix(matrix, k)
- set m = matrix.length
      n = matrix[0].length
      result = INT_MIN

- loop for i = 0; i < n; i++
  // initialize sum of size m with all values in it as 0
  - vector<int> sum(m, 0)

  - loop for j = i; j < n; j++
    - loop for r = 0; r < m; r++
      - update sum[r] = sum[r] + matrix[r][j]
    - for end
  - for end

  - set result = max(result, computeMaxSubarraySum(sum, k))
- for end

- return result

// computeMaxSubarraySum(sum, k)
- set currentSum = 0
      maxSum = INT_MIN

- create set sumValues and insert the value 0
  set<int> sumValues
  sumValues.insert(0)

- loop for i = 0; i < sum.size; i++
  - update currentSum = currentSum + x

  - set auto it = sumValues.lower_bound(currentSum - k)

  - if it != sumValues.end()
    - update maxSum = max(maxSum, currentSum - *it)
  - if end

  - sumValues.insert(currentSum)
- for end

- return maxSum

The time complexity of this approach is O(m * n ^ 2 * log(m)). Where m is the number of rows and n is the number of columns in the input matrix. The space complexity is O(n).

Let's check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int m = matrix.size(), n = matrix[0].size();
        int result = INT_MIN;

        for(int i = 0; i < n; i++) {
            vector<int> sum(m, 0);

            for(int j = i; j < n; j++) {
                for(int r = 0; r < m; r++) {
                    sum[r] += matrix[r][j];
                }

                result = max(result, computeMaxSubarraySum(sum, k));
            }
        }

        return result;
    }

    int computeMaxSubarraySum(vector<int> sum, int k) {
        int currentSum = 0;
        int maxSum = INT_MIN;
        set<int> sumValues;
        sumValues.insert(0);

        for(auto x: sum) {
            currentSum += x;

            auto it = sumValues.lower_bound(currentSum - k);
            if (it != sumValues.end()) {
                maxSum = max(maxSum, currentSum - *it);
            }

            sumValues.insert(currentSum);
        }

        return maxSum;
    }

};

Go solution

func maxSumSubmatrix(matrix [][]int, k int) int {
    m, n := len(matrix), len(matrix[0])
    sum := make([]int, n)
    sumValues := make(sortedIntSet, n)
    result := math.MinInt32

    for startRow := range matrix {
        for i := range sum {
            sum[i] = 0
        }

        for row := startRow; row < m; row++ {
            for col, val := range matrix[row] {
                sum[col] += val
            }

            currentSum := 0
            maxSum := sum[0]

            for _, val := range sum {
                currentSum = max(currentSum + val, val)
                maxSum = max(maxSum, currentSum)
            }

            if maxSum <= k {
                result = max(result, maxSum)
                continue
            }

            currentSum = 0
            sumValues = sumValues[:1]
            sumValues[0] = 0

            for _, val := range sum {
                currentSum += val

                partnerIdx := sort.SearchInts(sumValues, currentSum-k)

                if partnerIdx != len(sumValues) {
                    result = max(result, currentSum - sumValues[partnerIdx])
                }

                sumValues.insert(currentSum)
            }
        }
    }

    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

type sortedIntSet []int

func (s *sortedIntSet) insert(x int) {
    i := sort.SearchInts(*s, x)

    if i == len(*s) {
        *s = append(*s, x)
    } else if (*s)[i] != x {
        *s = append(*s, 0)
        copy((*s)[i+1:], (*s)[i:])
        (*s)[i] = x
    }
}

JavaScript solution

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var maxSumSubmatrix = function(matrix, k) {
    let m = matrix.length, n = matrix[0].length;
    let result = Number.MIN_VALUE;

    for(let i = 0; i < n; i++) {
        let sum = new Array(m).fill(0);

        for(let j = i; j < n; j++) {
            for(let r = 0; r < m; r++) {
                sum[r] += matrix[r][j];
            }

            result = Math.max(result, computeMaxSubarraySum(sum, k));
        }
    }

    return result;
};

var computeMaxSubarraySum = function(sum, k) {
    let currentSum = 0;
    let maxSum = Number.MIN_VALUE;
    let sumValues = new Set();
    sumValues.add(0);

    for(let r = 0; r < sum.length; r++) {
        currentSum += sum[r];

        let list = Array.from(sumValues);
        let it = list.lastIndexOf(currentSum - k)

        if (it > -1) {
            maxSum = Math.max(maxSum, currentSum - it);
        }

        sumValues.add(currentSum);
    }

    return maxSum;
};

Dry Run

Let's dry-run our algorithm to see how the solution works.

Input: matrix = [[1, 0, 1], [0, -2, 3]]
       k = 2

// maxSumSubmatrix(matrix, k)
Step 1: m = matrix.size()
          = 2
        n = matrix[0].size()
          = 3
        result = INT_MIN

Step 2: loop for i = 0; i < n
          0 < 3
          true

          vector<int> sum(m, 0)
          sum = [0, 0]

          loop for j = i; j < n; j++
            loop for r = 0; r < m; r++
              sum[r] = sum[r] + matrix[r][j]
            for end
          for end

          so after the above loop
          sum = [1, 0]

          result = max(result, computeMaxSubarraySum(sum, k))

// computeMaxSubarraySum(sum, 2)
// computeMaxSubarraySum([1, 0], 2)
Step 3: set currentSum = 0
            maxSum = INT_MIN
            set<int> sumValues
            sumValues.insert(0)

            loop for auto x: sum
              currentSum = currentSum + x
                         = 0 + 1
                         = 1

              sumValues = [0]
              it = sumValues.lower_bound(currentSum - k)
                 = sumValues.lower_bound(1 - 2)
                 = sumValues.lower_bound(-1)
                 = -1

              sumValues.add(currentSum)
              sumValues.add(1)
              sumValues = [0, 1]

            loop for auto x: sum
              currentSum = currentSum + x
                         = 1 + 0
                         = 1

              sumValues = [0, 1]
              it = sumValues.lower_bound(currentSum - k)
                 = sumValues.lower_bound(1 - 2)
                 = sumValues.lower_bound(-1)
                 = -1

Step 4: return maxSum
        return INT_MIN

// maxSumSubmatrix(matrix, k)
Step 5: result = max(result, computeMaxSubarraySum(sum, k))
               = max(INT_MIN, INT_MIN)
               = INT_MIN
        i++
        i = 1

Step 6: loop for i < n
          1 < 3
          true

          vector<int> sum(m, 0)
          sum = [0, 0]

          loop for j = i; j < n; j++
            loop for r = 0; r < m; r++
              sum[r] = sum[r] + matrix[r][j]
            for end
          for end

          so after the above loop
          sum = [0, -2]

          result = max(result, computeMaxSubarraySum(sum, k))

We compute the same steps for the whole matrix.

We return the result, and the answer is 2.

Maximum Gap

Alkesh Ghorpade — Sun, 25 Jun 2023 15:25:32 +0000

Problem statement

Given an integer array nums, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0.

You must write an algorithm that runs in linear time and uses linear extra space.

Problem statement taken from: https://leetcode.com/problems/maximum-gap.

Example 1:

Input: nums = [3, 6, 9, 1]
Output: 3
Explanation: The sorted form of the array is [1, 3, 6, 9], either (3, 6) or (6, 9) has the maximum difference 3.

Example 2:

Input: nums = [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Constraints:

- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^9

Solution

Approach 1: Brute force

The brute force approach sorts the array and finds the maximum difference between two adjacent elements. The time complexity of this approach is O(n), and the space complexity is O(1).

A C++ snippet of this approach is as below:

int maximumGap(vector<int>& nums) {
    int n = nums.size();

    if(n <= 1) {
        return 0;
    }

    sort(nums.begin(), nums.end());
    int maxDifference = INT_MIN;

    for(int i = 0; i < n - 1; i++) {
        maxDifference = max(maxDifference, nums[i + 1] - nums[i]);
    }

    return maxDifference;
}

Approach 2: Pigeonhole Sorting

The problem statement mentions solving the problem in linear time, using linear extra space. We can use the concept of Pigeonhole Sorting. Pigeonhole algorithm is suitable for sorting lists of elements where the number of elements and possible key values is approximately the same. It requires O(n + Range) time, where n is the number of elements in the input array and Range is the number of possible values in the array.

The flow of this algorithm is as follows:

- Find the minimum and maximum values in the array. We get the difference between the maximum and minimum value, which we call range. `range = maximum - minimum + 1`.

- Create an array of empty values (pigeonholes) with a size range.

- Iterate over the input array and insert each element in its pigeonhole. An element nums[i] is inserted in the hole at index nums[i] - min.

- Iterate over the pigeonhole array in order and insert the elements from the non-empty pigeonhole back into the original array.

We apply the above approach to find the maximum gap between two successive elements in the sorted array.

Let's check the algorithm.

Algorithm

- set maximum = nums[0]
      minimum = nums[0]
      n = nums.size()

- if n <= 1
  - return 0
- end if

- loop for i = 1; i < n; i++
  // set maximum and minimum
  - maximum = max(maximum, nums[i])
  - minimum = min(minimum, nums[i])
- end for

// create arrays to store maximum and minimum values in n-1 buckets of range
- vector<int> maxBucket(n - 1, INT_MIN)
- vector<int> minBucket(n - 1, INT_MAX)

// calculate the range
- range = ceil((maximum - minimum) / (n - 1))

// traverse through the input array and insert the element in the appropriate bucket
// if the bucket is empty else, update bucket values
- loop for i = 0; i < n; i++
  - if nums[i] == maximum || nums[i] == minimum
    - continue
  - end if

  // compute the index of the bucket
  - index = ((nums[i] - minimum) / range)

  - maxBucket[index] = max(maxBucket[index], nums[i])
  - minBucket[index] = min(minBucket[index], nums[i])
- end for

// find the maximum gap between the maximum value
// of the previous bucket minus a minimum of the current bucket.
- set previousValue = minimum
      maximumGap = 0

- loop for i = 0; i < n - 1; i++
  - if minBucket[i] == INT_MAX
    - continue
  - end if

  - maximumGap = max(maximumGap, minBucket[i] - previousValue)
  - previousValue = maxBucket[i]
- end for

- set maximumGap = max(maximumGap, maximum - previousValue)

- return maximumGap

The time complexity of this approach is O(n), and the space complexity if O(n).

Let's check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int maximum = nums[0], minimum = nums[0];
        int n = nums.size(), i;

        if(n <= 1) {
            return 0;
        }

        // find the maximum and minimum in nums[]
        for(int i = 1; i < n; i++) {
            maximum = max(maximum, nums[i]);
            minimum = min(minimum, nums[i]);
        }

        // create arrays to store maximum and minimum values in n-1 buckets of range.
        vector<int> maxBucket(n - 1, INT_MIN);
        vector<int> minBucket(n - 1, INT_MAX);

        // calculate the range
        int range = ceil((maximum - minimum) / (n - 1));

        // traverse through the input array and insert the element in the appropriate bucket
        // if the bucket is empty else, update bucket values
        for (i = 0; i < n; i++) {
            if (nums[i] == maximum || nums[i] == minimum)
                continue;

            // compute the index of the bucket
            int index = ((nums[i] - minimum) / range);

            maxBucket[index] = max(maxBucket[index], nums[i]);
            minBucket[index] = min(minBucket[index], nums[i]);
        }

        // find the maximum gap between the maximum value
        // of the previous bucket minus a minimum of the current bucket.
        int previousValue = minimum;
        int maximumGap = 0;

        for (i = 0; i < n - 1; i++) {
            if (minBucket[i] == INT_MAX)
                continue;

            maximumGap = max(maximumGap, minBucket[i] - previousValue);
            previousValue = maxBucket[i];
        }

        maximumGap = max(maximumGap, maximum - previousValue);

        return maximumGap;
    }
};

Go solution

func maximumGap(nums []int) int {
    maximum, minimum := nums[0], nums[0]
    n, i := len(nums), 0

    if n <= 1 {
        return 0
    }

    // find the maximum and minimum in nums[]
    for i = 1; i < n; i++ {
        maximum = max(maximum, nums[i])
        minimum = min(minimum, nums[i])
    }

    // create arrays to store maximum and minimum values in n-1 buckets of range.
    maxBucket := make([]int, n - 1)
    minBucket := make([]int, n - 1)

    for j := range maxBucket {
        maxBucket[j] = math.MinInt32
        minBucket[j] = math.MaxInt32
    }

    // calculate the range
    rangeValue := int(math.Ceil(float64(maximum - minimum) / float64(n - 1)))

    // traverse through the input array and insert the element in the appropriate bucket
    // if the bucket is empty else, update bucket values
    for i = 0; i < n; i++ {
        if nums[i] == maximum || nums[i] == minimum {
            continue
        }

        index := ((nums[i] - minimum) / rangeValue)

        maxBucket[index] = max(maxBucket[index], nums[i])
        minBucket[index] = min(minBucket[index], nums[i])
    }

    // find the maximum gap between the maximum value
    // of the previous bucket minus a minimum of the current bucket
    previousValue, maximumGap := minimum, 0

    for i = 0; i < n - 1; i++ {
        if minBucket[i] == math.MaxInt32 {
            continue
        }

        maximumGap = max(maximumGap, minBucket[i] - previousValue)
        previousValue = maxBucket[i]
    }

    return max(maximumGap, maximum - previousValue)
}

func max(a, b int) int {
    if a > b {
        return a
    }

    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }

    return b
}

JavaScript solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumGap = function(nums) {
    let maximum = nums[0], minimum = nums[0];
    let n = nums.length, i;

    if(n <= 1) {
        return 0;
    }

    // find the maximum and minimum in nums[]
    for(i = 1; i < n; i++) {
        maximum = Math.max(maximum, nums[i]);
        minimum = Math.min(minimum, nums[i]);
    }

    // create arrays to store maximum and minimum values in n-1 buckets of range.
    let maxBucket = new Array(n - 1).fill(Number.MIN_SAFE_INTEGER);
    let minBucket = new Array(n - 1).fill(Number.MAX_SAFE_INTEGER);

    // calculate the range
    let range = Math.ceil((maximum - minimum) / (n - 1));

    // traverse through the input array and insert the element in the appropriate bucket
    // if the bucket is empty else, update bucket values
    for (i = 0; i < n; i++) {
        if (nums[i] == maximum || nums[i] == minimum)
            continue;

        // compute the index of the bucket
        let index = ((nums[i] - minimum) / range);

        maxBucket[index] = Math.max(maxBucket[index], nums[i]);
        minBucket[index] = Math.min(minBucket[index], nums[i]);
    }

    // find the maximum gap between the maximum value
    // of the previous bucket minus a minimum of the current bucket.
    let previousValue = minimum;
    let maximumGap = 0;

    for (i = 0; i < n - 1; i++) {
        if (minBucket[i] == Number.MAX_SAFE_INTEGER)
            continue;

        maximumGap = Math.max(maximumGap, minBucket[i] - previousValue);
        previousValue = maxBucket[i];
    }

    maximumGap = Math.max(maximumGap, maximum - previousValue);

    return maximumGap;
};

Dry Run

Let's dry-run our algorithm to see how the solution works.

Input: nums = [3, 6, 9, 1]

Step 1: maximum = nums[0]
                = 3
        minimum = nums[0]
                = 3
        n = nums.size()
          = 4

Step 2: if n <= 1
           4 <= 1
           false

Step 3: // find the maximum and minimum in nums[]
        loop for int i = 1; i < n; i++

        // at the end of this loop we get max
        // and min
        maximum = 9
        minimum = 1

Step 4: vector<int> maxBucket(n - 1, INT_MIN)
        maxBucket = [INT_MIN, INT_MIN, INT_MIN]

        vector<int> minBucket(n - 1, INT_MAX)
        minBucket = [INT_MAX, INT_MAX, INT_MAX]

Step 5: range = ceil((maximum - minimum) / (n - 1))
              = ceil(9 - 1 / 4 - 1)
              = ceil(8 / 3)
              = 2

Step 6: loop for i = 0; i < n
          0 < 4
          true

          if nums[i] == maximum || nums[i] == minimum
             nums[0] == 9 || nums[0] == 1
             3 == 9 || 3 == 1
             false

          index = ((nums[i] - minimum) / range)
                = ((nums[0] - 1) / 2)
                = (3 - 1) / 2
                = 1

          maxBucket[index] = max(maxBucket[index], nums[i])
          maxBucket[1] = max(maxBucket[1], nums[0])
                       = max(INT_MIN, 3)
                       = 3
          maxBucket = [INT_MIN, 3, INT_MIN]

          minBucket[index] = min(minBucket[index], nums[i])
          minBucket[1] = max(minBucket[1], nums[0])
                       = max(INT_MAX, 3)
                       = 3
          minBucket = [INT_MAX, 3, INT_MIN]

          i++
          i = 1

        loop for i < 4
          1 < 4
          true

          if nums[i] == maximum || nums[i] == minimum
            nums[1] == 9 || nums[1] == 1
            6 == 9 || 6 == 1
            false

          index = ((nums[i] - minimum) / range)
                = ((nums[1] - 1) / 2)
                = (6 - 1) / 2
                = 2

          maxBucket[index] = max(maxBucket[index], nums[i])
          maxBucket[2] = max(maxBucket[2], nums[1])
                       = max(INT_MIN, 6)
                       = 6
          maxBucket = [INT_MIN, 3, 6]

          minBucket[index] = min(minBucket[index], nums[i])
          minBucket[2] = max(minBucket[2], nums[1])
                       = max(INT_MAX, 6)
                       = 6
          minBucket = [INT_MAX, 3, 6]

          i++
          i = 2

        loop for i < 4
          2 < 4
          true

          if nums[i] == maximum || nums[i] == minimum
            nums[2] == 9 || nums[2] == 1
            9 == 9 || 9 == 1
            true
            continue

          i++
          i = 3

        loop for i < 4
          3 < 4
          true

          if nums[i] == maximum || nums[i] == minimum
            nums[3] == 9 || nums[3] == 1
            1 == 9 || 1 == 1
            true
            continue

          i++
          i = 4

        loop for i < 4
          4 < 4
          false

Step 7: previousValue = minimum
                      = 1
        maximumGap = 0

Step 8: loop for i = 0; i < n - 1
          0 < 4 - 1
          0 < 3
          true

          if minBucket[i] == INT_MAX
             minBucket[0] == INT_MAX
             true

             continue

          i++
          i = 1

        loop for i < n - 1
          1 < 4 - 1
          1 < 3
          true

          if minBucket[i] == INT_MAX
             minBucket[1] == INT_MAX
             3 == INT_MAX
             false

          maximumGap = max(maximumGap, minBucket[i] - previousValue)
                     = max(0, minBucket[1] - previousValue)
                     = max(0, 3 - 1)
                     = max(0, 2)
                     = 2

          previousValue = maxBucket[i]
                        = maxBucket[1]
                        = 3

          i++
          i = 2

        loop for i < n - 1
          2 < 4 - 1
          2 < 3
          true

          if minBucket[i] == INT_MAX
             minBucket[1] == INT_MAX
             6 == INT_MAX
             false

          maximumGap = max(maximumGap, minBucket[i] - previousValue)
                     = max(2, minBucket[2] - previousValue)
                     = max(2, 6 - 3)
                     = max(2, 3)
                     = 3

          previousValue = maxBucket[i]
                        = maxBucket[2]
                        = 6

          i++
          i = 3

        loop for i < n - 1
          3 < 4 - 1
          3 < 3
          false

Step 9: maximumGap = max(maximumGap, maximum - previousValue)
                   = max(3, 9 - 6)
                   = max(3, 3)
                   = 3

Step 10: return maximumGap

We return the answer as 3.

Odd Even Linked List

Alkesh Ghorpade — Thu, 22 Jun 2023 12:29:31 +0000

Problem statement

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Problem statement taken from: https://leetcode.com/problems/odd-even-linked-list.

Example 1:

Input: head = [1, 2, 3, 4, 5]
Output: [1, 3, 5, 2, 4]

Example 2:

Input: head = [2, 1, 3, 5, 6, 4, 7]
Output: [2, 3, 6, 7, 1, 5, 4]

Constraints:

- The number of nodes in the linked list is in the range [0, 10^4].
- -10^6 <= Node.val <= 10^6

Solution

Approach 1: Using additional

The naive approach is to create two separate linked lists, one for the odd-indices nodes and the other for the even-indices nodes. We iterate the original linked list, and for each node, we will check the node's position using a counter. If the linked list position node is odd, we append it to the odd-indices linked list, or if the position is even, we append it to the even-indices linked list. Once the complete linked list is traversed, we append the even-indices linked list at the end of the odd-indices linked list.

A C++ snippet of this approach is as follows:

ListNode* oddEvenList(ListNode* head) {
    // initialize oddHead and evenHead pointers
    ListNode* oddHead = new ListNode(0);
    ListNode* odd = oddHead;
    ListNode* evenHead = new ListNode(0);
    ListNode* even = evenHead;
    ListNode* currend = head;
    int counter = 1;

    // traverse the linked list till the end
    while(current) {
        // odd-indices node
        if(counter % 2 == 1) {
            odd->next = current;
            odd = odd->next;
        } else {
            // even-indices node
            even->next = current;
            even = even->next;
        }

        current = current->next;
        counter++;
    }

    // append even-indices linked list
    // at the end of the odd-indices linked list
    odd->next = evenHead->next;
    even->next = NULL;

    return oddHead->next;
};

The time complexity of the above algorithm is O(n), and the space complexity is O(1).

Approach 2: Sorting in-place

We can tweak the above algorithm to solve the odd-even linked list problem. The counter variable can be eliminated, and instead of pointing the oddHead and evenHead to a new node, we can point them to head and head->next, respectively.

When working on the solution, it’s important to ensure we are covering all the edge cases.

Empty linked list or a linked list with a single node.
A linked list with only two nodes.
A linked list with odd numbers of nodes.
A linked list with an even number of nodes.

Let's check the algorithm first.

Algorithm

// if the list is empty or has only one node
- if head == NULL || head->next == NULL
  - return head
- end if

// initialize the odd and even pointers
- oddPointer = head
  evenPointer = head->next
  evenHead = head->next

// loop while even pointer is not NULL
// or even pointer next is not NULL
- loop while evenPointer != NULL && evenPointer->next != NULL

  // skip the next node and point the current odd index node to
  // the next odd index node
  - oddPointer->next = oddPointer->next->next
  - oddPointer = oddPointer->next

  // skip the next node and point the current even index node to
  // the even odd index node
  - evenPointer->next = evenPointer->next->next
  - evenPointer = evenPointer->next
- while end

- oddPointer->next = evenHead

- return head

We initialized three-pointers oddPointer, evenPointer and evenHead. oddPointer will point to the head and the evenPointer will point to the head's next node. In each iteration, the oddPointer and evenPointer will skip the next node point to the next odd and even index node. Once the iteration over the linked list is done, we point the oddPointer next to the start of evenHead.

The time complexity of the above algorithm is O(n), and the space complexity is O(1).

Let's check out our solutions in C++, Golang, and Javascript.

C++ solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        // if the list is empty or has only one node
        if(head == NULL || head->next == NULL) {
            return head;
        }

        // initialize the odd and even pointers
        ListNode* oddPointer = head;
        ListNode* evenPointer = head->next;
        ListNode* evenHead = head->next;

        // loop while even pointer is not NULL
        // or even pointer next is not NULL
        while(evenPointer != NULL && evenPointer->next != NULL) {

            // skip the next node and point the current odd index node to
            // the next odd index node
            oddPointer->next = oddPointer->next->next;
            oddPointer = oddPointer->next;

            // skip the next node and point the current even index node to
            // the even odd index node
            evenPointer->next = evenPointer->next->next;
            evenPointer = evenPointer->next;
        }

        oddPointer->next = evenHead;

        return head;
    }
};

Go solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func oddEvenList(head *ListNode) *ListNode {
    // if the list is empty or has only one node
    if head == nil || head.Next == nil {
        return head
    }

    // initialize the odd and even pointers
    oddPointer, evenPointer, evenHead := head, head.Next, head.Next

    // loop while even pointer is not NULL
    // or even pointer next is not NULL
    for evenPointer != nil && evenPointer.Next != nil {
        // skip the next node and point the current odd index node to
        // the next odd index node
        oddPointer.Next = oddPointer.Next.Next
        oddPointer = oddPointer.Next

        // skip the next node and point the current even index node to
        // the even odd index node
        evenPointer.Next = evenPointer.Next.Next
        evenPointer = evenPointer.Next
    }

    oddPointer.Next = evenHead

    return head
}

JavaScript solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function(head) {
    // if the list is empty or has only one node
    if(head == null || head.next == null) {
        return head;
    }

    // initialize the odd and even pointers
    let oddPointer = head;
    let evenPointer = head.next;
    let evenHead = head.next;

    // loop while even pointer is not NULL
    // or even pointer next is not NULL
    while(evenPointer != null && evenPointer.next != null) {
        // skip the next node and point the current odd index node to
        // the next odd index node
        oddPointer.next = oddPointer.next.next;
        oddPointer = oddPointer.next;

        // skip the next node and point the current even index node to
        // the even odd index node
        evenPointer.next = evenPointer.next.next;
        evenPointer = evenPointer.next;
    }

    oddPointer.next = evenHead;

    return head;
};

Dry Run

Let's dry-run our algorithm to see how the solution works.

Input: head = [1, 2, 3, 4, 5]

Step 1: if head == NULL || head->next == NULL
           head -> 1
           head->next -> 2
           false

Step 2: ListNode* oddPointer = head
                  oddPointer -> 1

        ListNode* evenPointer = head->next
                  evenPointer -> 2

        ListNode* evenHead = head->next
                  evenHead -> 2

Step 3: loop while evenPointer != NULL && evenPointer->next != NULL
          evenPointer -> 2
          evenPointer->next -> 4

          2 != NULL && 4 != NULL
          true

          oddPointer->next = oddPointer->next->next
          oddPointer->next -> 2
          oddPointer->next->next -> 3

          oddPointer -> 1 -> 3

          oddPointer = oddPointer->next
          oddPointer -> 3

          evenPointer->next = evenPointer->next->next
          evenPointer->next -> 3
          evenPointer->next->next -> 4

          evenPointer -> 2 -> 4

          evenPointer = evenPointer->next
          evenPointer -> 4

Step 4: loop while evenPointer != NULL && evenPointer->next != NULL
          evenPointer -> 4
          evenPointer->next -> 5

          2 != NULL && 5 != NULL
          true

          oddPointer->next = oddPointer->next->next
          oddPointer->next -> 4
          oddPointer->next->next -> 5

          oddPointer -> 1 -> 3 -> 5

          oddPointer = oddPointer->next
          oddPointer -> 5

          evenPointer->next = evenPointer->next->next
          evenPointer->next -> 5
          evenPointer->next->next -> NULL

          evenPointer -> 2 -> 4 -> NULL

          evenPointer = evenPointer->next
          evenPointer -> NULL

Step 5: loop while evenPointer != NULL && evenPointer->next != NULL
          evenPointer -> NULL

          NULL != NULL
          false

Step 6: oddPointer->next = evenHead
        1 -> 3 -> 5 -> 2 -> 4

Step 7: return head

We return the answer as 1 -> 3 -> 5 -> 2 -> 4.

Sudoku Solver

Alkesh Ghorpade — Thu, 15 Jun 2023 19:20:41 +0000

Problem statement

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
The '.' character indicates empty cells.

Problem statement taken from: https://leetcode.com/problems/sudoku-solver.

Example 1:

Input: board = [['5', '3', '.', '.', '7', '.', '.', '.', '.'],
  ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
  ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
  ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
  ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
  ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
  ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
  ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
  ['.', '.', '.', '.', '8', '.', '.', '7', '9']
]

Output: [['5', '3', '4', '6', '7', '8', '9', '1', '2'],
  ['6', '7', '2', '1', '9', '5', '3', '4', '8'],
  ['1', '9', '8', '3', '4', '2', '5', '6', '7'],
  ['8', '5', '9', '7', '6', '1', '4', '2', '3'],
  ['4', '2', '6', '8', '5', '3', '7', '9', '1'],
  ['7', '1', '3', '9', '2', '4', '8', '5', '6'],
  ['9', '6', '1', '5', '3', '7', '2', '8', '4'],
  ['2', '8', '7', '4', '1', '9', '6', '3', '5'],
  ['3', '4', '5', '2', '8', '6', '1', '7', '9']
]

Explanation: The input board is shown above and the only valid solution is shown below:

Constraints:

- board.length == 9
- board[i].length == 9
- board[i][j] is a digit or '.'
- It is guaranteed that the input board has only one solution.

Solutions for Sudoku Solver

Approach 1: Sudoku using Brute Force

The naive approach is to generate all possible numbers 1 to 9 configurations to fill the empty cells. We try every combination one by one until we get a valid sudoku. For every empty cell, we fill the position with numbers from 1 to 9. Once the sudoku is filled, we check if the sudoku is valid or not. If the sudoku is invalid, we recur for other cases.

A C++ snippet of this approach is as follows:

class Solution {
public:
    bool isValid(vector<vector<char>>& board, int i, int j, char value){
        // check for a valid row
        for(int row = 0; row < 9; row++) {
            if(board[row][j] == value) {
                return false;
            }
        }

        // check for a valid column
        for(int col = 0; col < 9; col++) {
            if(board[i][col] == value) {
                return false;
            }
        }

        // check for a valid 3 * 3 matrix
        for(int k = 0; k < 9; k++) {
            if(board[3 * (i / 3) + k % 3][3 * (j / 3) + k / 3] == value) {
                return false;
            }
        }

        return true;
    }

    bool solveSudokuHelper(vector<vector<char>>& board, int row, int column) {
        // if we reached the last cell of the board
        // we should avoid further backtracking
        // return true in this case
        if (row == 8 && column == 9)
            return true;

        // if the column value becomes 9,
        // we move to the next row
        if (column == 9) {
            row++;
            column = 0;
        }

        // if the current cell of the board already contains
        // any value from 1-9, we iterate for the next column
        if (board[row][column] != '.')
            return solveSudokuHelper(board, row, column + 1);

        for (int num = 1; num <= 9; num++) {
            // Check if it is safe to place
            // the num (1-9) in the
            // given cell
            if (isValid(board, row, column, num)) {
                // assign the value to the corresponding cell
                board[row][column] = char(num);

                // fill in the values for the next column
                if (solveSudokuHelper(board, row, column + 1))
                    return true;
            }

            // if, in the previous step, the sudoku was invalid
            // update the cell to an empty value. In this case, '.'
            board[row][column] = '.';
        }

        return false;
    }

    void solveSudoku(vector<vector<char>>& board) {
        solveSudokuHelper(board, 0, 0);
    }
};

The time complexity of this approach is O(9 ^ (n * n)). We are filling every empty cell of the board with all 9 possible combinations.

The space complexity is O(1).

Approach 2: Sudoku using Backtracking

Sudoku is solved by assigning numbers one by one to empty cells. In this approach, we first check if assigning a number to the cell is safe. If the placement is valid, we then move to the next column. To validate the cell value, we check if the number is not present in the current row, column, or 3 * 3 subgrid. After validating the cell, we recursively check whether this assignment leads to the solution. We try the next number if the assignment doesn't lead to a solution.

The code flow of this approach is as follows:

- Create a HashMap for the row, column and 3 * 3 subgrid.
- Create a function that validates the assignment of the current cell of the grid.
- If any number from 1-9 has a value greater than 1 in the HashMap, return false else, return true.
- Create a recursive function that accepts the sudoku board as a param.
- Check for an empty cell ('.')
  - if the cell is empty, assign a number from 1 to 9
  - check if assigning the number to the current cell, makes the sudoku safe or not
  - if the sudoku is valid, recursively call the function for all safe cases from 0 to 9.
  - if any recursive call returns true, we end the loop.

A C++ snippet of this approach is as below:

class Solution {
public:
    bool numPresentInRow(vector<vector<char>>& board, int row, int num) {
        for (int column = 0; column < 9; column++)
            if (grid[row][column] == num)
                return true;

        return false;
    }

    bool numPresentInColum(vector<vector<char>>& board, int column, int num) {
        for (int row = 0; row < 9; row++)
            if (grid[row][column] == num)
                return true;

        return false;
    }

    bool numPresentInSubGrid(vector<vector<char>>& board, int subGridRowStartIndex, int subGridColumnStartIndex, int num) {
        for (int row = 0; row < 3; row++)
            for (int col = 0; col < 3; col++)
                if (grid[row + subGridRowStartIndex][col + subGridColumnStartIndex] == num)
                    return true;

        return false;
    }

    bool isSafe(vector<vector<char>>& board, int row, int column, char num) {
        return !numPresentInRow(board, row, num)
           && !numPresentInColum(board, column, num)
           && !numPresentInSubGrid(board, row - row % 3, column - column % 3, num)
           && board[row][column] == '.';
    }

    // function to check if there are any empty cells in the sudoku
    // if yes, the row and column parameters (passed by reference)
    // will be set to the location that is empty and true is returned
    bool hasEmptyCell(vector<vector<char>>& board, int& row, int& column) {
        for (row = 0; row < 9; i++)
            for (column = 0; column < 9; column++)
                if (grid[row][column] == '.')
                    return true;

        return false;
    }

    bool solveSudokuHelper(vector<vector<char>>& board) {
        int row, column;

        // return true if there are no empty cells
        if (!hasEmptyCell(board, row, column))
            return true;

        // loop from 1 to 9
        for (int num = 1; num <= 9; num++) {
            // check if the assignment of num is safe
            if (isSafe(board, row, column, num)) {
                // make a tentative assignment
                board[row][column] = char(num);

                // return true if the current assignment is valid
                if (solveSudokuHelper(board))
                    return true;

                // if the assignment is unsafe,
                // assign the empty value
                board[row][column] = '.';
            }
        }

        // this triggers backtracking
        return false;
    }

    void solveSudoku(vector<vector<char>>& board) {
        solveSudokuHelper(board);
    }
};

The worst-case time complexity of this approach remains the same as the Brute Force approach, that is O(9 ^ (n * n)). But since we are validating the assignment, we are avoiding a few unnecessary iterations; hence, the average-case time complexity will be better.

Approach 3: Sudoku using BitMask

This approach is a slight optimization to the Backtracing solution. Instead of looping over each row, column and subgrid to check whether the number is already present, we use bit masks to verify the same.

Let's check the algorithm first.

Algorithm

// function solveSudoku(board)
- set vector<int> rows(9, 0), columns(9, 0), subgrids(9, 0)

// this will mask the bits in the row, columns and subgrids array
// for non-empty cells
- call setBits(board, rows, columns, subgrids)

// function to backtrack and generate the possible solutions
- backtrack(board, index, rows, columns, subgrids)


// function setBits(board, rows, columns, subgrids)
- loop for row = 0; row < 9; row++
  - loop for column = 0; column < 9; column++
    - if board[row][column] != '.'
      - set bitMask = 1 << (board[row][column] - '1')
      - set subgrid = (row / 3) * 3 + (column / 3)

      // mask the values in the row, column and subgrid array
      - rows[row] |= bitMask
      - columns[column] |= bitMask
      - subgrids[subgrid] |= bitMask
    - end if
  - end inner for loop
- end outer for loop

Check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    void setBits(vector<vector<char>>& board, vector<int>& rows, vector<int>& columns, vector<int>& subgrids) {
        for(int row = 0; row < 9; row++) {
            for(int column = 0; column < 9; column++) {
                if(board[row][column] != '.') {
                    int bitMask = 1 << (board[row][column] - '1');
                    int subgrid = (row / 3) * 3 + (column / 3);

                    rows[row] |= bitMask;
                    columns[column] |= bitMask;
                    subgrids[subgrid] |= bitMask;
                }
            }
        }
    }

    bool backtrack(vector<vector<char>>& board, int index, vector<int>& rows, vector<int>& columns, vector<int>& subgrids) {
        if (index > 80)
            return true;

        int row = index / 9;
        int column = index % 9;

        if (board[row][column] != '.')
            return backtrack(board, index + 1, rows, columns, subgrids);

        int subgrid = (row / 3) * 3 + (column / 3);

        for (int i = 0; i < 9; ++i) {
            int mask = 1 << i;
            if (rows[row] & mask || columns[column] & mask || subgrids[subgrid] & mask)
                continue;

            board[row][column] = i + '1';
            rows[row] |= mask;
            columns[column] |= mask;
            subgrids[subgrid] |= mask;

            if (backtrack(board, index + 1, rows, columns, subgrids))
                return true;

            board[row][column] = '.';
            rows[row] ^= mask;
            columns[column] ^= mask;
            subgrids[subgrid] ^= mask;
        }

        return false;
    }

    void solveSudoku(vector<vector<char>>& board) {
        vector<int> rows(9, 0), columns(9, 0), subgrids(9, 0);

        setBits(board, rows, columns, subgrids);

        backtrack(board, 0, rows, columns, subgrids);
    }
};

Golang solution

func setBits(board [][]byte, rows []int, columns []int, subgrids []int) {
    for row := 0; row < 9; row++ {
        for column := 0; column < 9; column++ {
            if board[row][column] != '.' {
                bitMask := 1 << (board[row][column] - '1')
                subgrid := (row / 3) * 3 + (column / 3)

                rows[row] |= bitMask
                columns[column] |= bitMask
                subgrids[subgrid] |= bitMask
            }
        }
    }
}

func backtrack(board [][]byte, index int, rows []int, columns []int, subgrids []int) bool {
    if index > 80 {
        return true
    }

    row := index / 9
    column := index % 9

    if board[row][column] != '.' {
        return backtrack(board, index + 1, rows, columns, subgrids)
    }

    subgrid := (row / 3) * 3 + (column / 3)

    for i := 0; i < 9; i++ {
        mask := 1 << i

        if (rows[row] & mask != 0) || (columns[column] & mask != 0) || (subgrids[subgrid] & mask != 0) {
            continue
        }

        board[row][column] = byte(i + 1 + '0')
        rows[row] |= mask
        columns[column] |= mask
        subgrids[subgrid] |= mask

        if backtrack(board, index + 1, rows, columns, subgrids) {
            return true
        }

        board[row][column] = '.'
        rows[row] ^= mask
        columns[column] ^= mask
        subgrids[subgrid] ^= mask
    }

    return false
}

func solveSudoku(board [][]byte)  {
    rows, columns, subgrids := make([]int, 9), make([]int, 9), make([]int, 9)

    setBits(board, rows, columns, subgrids)

    backtrack(board, 0, rows, columns, subgrids)
}

JavaScript solution

var setBits = function(board, rows, columns, subgrids) {
    for(let row = 0; row < 9; row++) {
        for(let column = 0; column < 9; column++) {
            if(board[row][column] != '.') {
                let bitMask = 1 << (parseInt(board[row][column]) - 1);
                let subgrid = Math.floor(row / 3) * 3 + Math.floor(column / 3);

                rows[row] |= bitMask;
                columns[column] |= bitMask;
                subgrids[subgrid] |= bitMask;
            }
        }
    }
}

var backtrack = function(board, index, rows, columns, subgrids) {
    if (index > 80)
            return true;

    let row = Math.floor(index / 9);
    let column = Math.floor(index % 9);

    if (board[row][column] != '.')
        return backtrack(board, index + 1, rows, columns, subgrids);

    let subgrid = Math.floor(row / 3) * 3 + Math.floor(column / 3);

    for (let i = 0; i < 9; ++i) {
        let mask = 1 << i;
        if (rows[row] & mask || columns[column] & mask || subgrids[subgrid] & mask)
            continue;

        board[row][column] = (i + 1).toString();
        rows[row] |= mask;
        columns[column] |= mask;
        subgrids[subgrid] |= mask;

        if(backtrack(board, index + 1, rows, columns, subgrids))
            return true;

        board[row][column] = '.';
        rows[row] ^= mask;
        columns[column] ^= mask;
        subgrids[subgrid] ^= mask;
    }

    return false;
}

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
    let rows = Array(9).fill(0), columns = Array(9).fill(0), subgrids = Array(9).fill(0);

    setBits(board, rows, columns, subgrids);

    backtrack(board, 0, rows, columns, subgrids);
};

Implement LRU Cache

Alkesh Ghorpade — Sun, 11 Jun 2023 13:15:22 +0000

Problem statement

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Problem statement taken from: https://leetcode.com/problems/lru-cache.

Example 1:

Input
['LRUCache', 'put', 'put', 'get', 'put', 'get', 'put', 'get', 'get', 'get']
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1 = 1}
lRUCache.put(2, 2); // cache is {1 = 1, 2 = 2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1 = 1, 3 = 3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4 = 4, 3 = 3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Constraints:

- 1 <= capacity <= 3000
- 0 <= key <= 10^4
- 0 <= value <= 10^5
- At most 2 * 10^5 calls will be made to get and put.

What is an LRU cache?

A cache provides a high-speed data storage layer which stores a subset of data. It ensures future requests for the same data get served faster than fetching the data from the primary storage location.

When our application's data size is vast, we cannot cache the whole data. Caching complete data is also not optimal and cost-effective, so we only store the subset of data in the cache. But what data goes into the cache depends entirely on the application, because of which we have different caching mechanisms.

A Least Recently Used (LRU) cache is one such type of caching. LRU is a cache eviction algorithm that organizes the elements in order of use. LRU will remove the element that has not been referenced or used for a long time.

Source: Geeksforgeeks

As seen in the above image, the cache size is 3, and initially, it's empty. We add 1 to the cache, and it gets stored at the beginning of the cache. We next add 2 and 3 to the cache. 3 gets added at the front of the cache list, and 1 gets stored at the tail of the cache. When we try to add 1 to the cache again, we see the cache is full. The least recently used element, which is 2, is present at the tail end of the cache. We remove the element and insert 1 at the front of the cache.

How to implement an LRU cache?

As seen in the above image, we know that the elements get added to a queue, and we follow FIFO (First-In-First-Out) approach.

We need to use the Queue data structure. The queue will have a limited capacity.
Whenever an element gets added, we add it to the head of the queue.
When the queue size is complete, and we want to add a new element, we pop the elements from the tail of the queue.
Adding and removing the elements to the queue must be done in constant time. It can be solved using a Doubly Linked List.
Since it's a cache, we also need to ensure the element we are looking for can be fetched quickly, in O(1) time. It can be done using a HashMap. Apart from storing elements in the doubly linked list, we also store them in the HashMap.

LRU cache will be a combination of Doubly Linked List and HashMap.

Algorithm for LRU

We need to follow these basic steps since we know what data structures to use for implementing an LRU.

If the key is present in the HashMap, we call that a cache hit, and we return the value
If the key is absent, it's a cache-miss; we must follow these two steps a. Add the new element in front of the queue. b. Add a new entry for the element in the HashMap and update the head.
If it's a cache-hit a. We remove the element from the queue and add it as the head of the queue. b. We update the HashMap with a new reference to the head of the list.

Let's check the algorithm below:

Algorithm

// define a Node struct
- struct Node {
      // since it's a doubly linked list, a node will have two pointers
      // next and prev that stores the address of the next and previous nodes
      // of the linked list.

      // key is the element we search
      // value is the data we want to store in the cache for this key
      Public: {
          Node *next;
          Node *prev;
          int value;
          int key;
      }
  }

// define the class LRU Cache
- class LRUCache
    Public: {
        // initialize the head and tail of the doubly linked list
        Node *head = new Node()
        Node *tail = new Node()

        // create a HashMap that stores the element and helps in fetching
        // the data in **O(1)** time.
        unordered_map<int, Node*> nodeMap

        // the size of the doubly linked list
        int capacity

        // function to initialize the LRU cache class
        // Since the cache is empty
        // we point the head next to tail and tail previous to head
        LRUCache(int capacity) {
            this->capacity = capacity;
            head->next = tail;
            tail->prev= head;
        }

        // function to get the element from the cache
        // the function expects a key element
        int get(int key) {
            // if the element is present in the cache, a cache-hit
            // we remove the element from the doubly linked list
            // and place it at the head of the list.

            // if it's a cache hit, in this case, we just return -1.

            if(nodeMap.find(key) != nodeMap.end()){
                Node* node = nodeMap[key];
                removeNode(node);
                addNode(node);
                return node->value;
            } else {
                return -1;
            }
        }

        // function to add the element in the cache
        void put(int key, int value) {
            // if the key is present in the cache
            // we update the value associated with the key.
            // We remove the node from the list
            // and since it was recently searched, we update
            // it as the head of the queue

            // if the key is not present in the cache
            // we first check if the cache is full
            // if the cache is full we remove the tail from the
            // list and remove the associated key from the hash map,
            // since it was not searched recently.

            // we add the new element as the head of the cache
            // and create an entry in the hash map
            if(nodeMap.find(key) != nodeMap.end()){
                Node* node = nodeMap[key];
                node->value = value;
                removeNode(node);
                addNode(node);
            } else {
                if(nodeMap.size() == capacity) {
                    Node* node = tail->prev;
                    removeNode(node);
                    nodeMap.erase(node->key);
                }

                Node* node = new Node();
                node->value = value;
                node->key = key;
                addNode(node);
                nodeMap[key] = node;
            }
        }

        // function to create a new entry in the list
        // the new element will be head of the list
        void addNode(Node* node){
            node->next = head->next;
            node->prev = head;
            (node->next)->prev = node;
            head->next = node;
        }

        // function to remove the tail node from the list
        void removeNode(Node* node){
            Node* prevNode = node->prev;
            Node* nextNode = node->next;
            prevNode->next = nextNode;
            nextNode->prev = prevNode;
        }
    }

The time complexity for searching, adding and deleting an element is O(1). The space complexity is O(n) since we are using an additional space HashMap and a Doubly Linked list.

Check out our solutions in C++, Golang, and JavaScript.

C++ solution

struct Node{
    public:
        Node* next;
        Node* prev;
        int value;
        int key;
};

class LRUCache {
public:
    Node* head = new Node();
    Node* tail = new Node();
    unordered_map<int, Node*> nodeMap;
    int capacity;

    LRUCache(int capacity) {
        this->capacity = capacity;
        head->next = tail;
        tail->prev= head;
    }

    int get(int key) {
        if(nodeMap.find(key) != nodeMap.end()){
            Node* node = nodeMap[key];
            removeNode(node);
            Node* temp = head;
            addNode(node);
            temp = head;
            temp = tail;
            return node->value;
        } else {
            Node* temp = head;
            temp = tail;
            return -1;
        }
    }

    void put(int key, int value) {
        if(nodeMap.find(key) != nodeMap.end()){
            Node* node = nodeMap[key];
            node->value = value;
            removeNode(node);
            addNode(node);
        } else {
            if(nodeMap.size() == capacity) {
                Node* node = tail->prev;
                removeNode(node);
                nodeMap.erase(node->key);
            }

            Node* node = new Node();
            node->value = value;
            node->key = key;
            addNode(node);
            Node* temp = head;
            temp=tail;
            nodeMap[key] = node;
        }
    }

    void addNode(Node* node){
        node->next = head->next;
        node->prev = head;
        (node->next)->prev = node;
        head->next = node;
        Node* temp = head;
    }

    void removeNode(Node* node){
        Node* prevNode = node->prev;
        Node* nextNode = node->next;
        prevNode->next = nextNode;
        nextNode->prev = prevNode;
        Node* temp = head;
        temp = tail;
    }
};

Golang solution

type Node struct {
    next *Node
    prev *Node
    value int
    key int
}

type LRUCache struct {
    nodeMap map[int]*Node
    head, tail *Node
    capacity int
}

func Constructor(capacity int) LRUCache {
    head := &Node{nil, nil, 0, 0}
    tail := &Node{nil, nil, 0, 0}
    head.next = tail
    tail.next = head

    return LRUCache {
        capacity: capacity,
        nodeMap: make(map[int]*Node),
        head: head,
        tail: tail,
    }
}

func (this *LRUCache) Get(key int) int {
    if node, ok := this.nodeMap[key]; ok {
        this.removeNode(node)
        this.addNode(node)
        return node.value
    } else {
        return -1
    }
}

func (this *LRUCache) Put(key int, value int)  {
    if node, ok := this.nodeMap[key]; ok {
        node.value = value
        this.removeNode(node)
        this.addNode(node)
    } else {
        if len(this.nodeMap) == this.capacity {
            node = this.tail.prev
            this.removeNode(node)
            delete(this.nodeMap, node.key)
        }

        node := &Node{nil, nil, 0, 0}
        node.value = value
        node.key = key
        this.addNode(node)
        this.nodeMap[key] = node
    }
}

func (this *LRUCache) addNode(node *Node) {
    node.prev = this.head
    node.next = this.head.next
    node.next.prev = node
    this.head.next = node
}

func (this *LRUCache) removeNode(node *Node) {
    prevNode := node.prev
    nextNode := node.next
    prevNode.next = nextNode
    nextNode.prev = prevNode
}

JavaScript solution

class Node {
    /**
     * @param {number} value
     * @param {Node} prev
     * @param {Node} next
     * @return {void}
     */
    constructor(key = 0, value = 0, prev = null, next = null) {
        this.key = key;
        this.value = value;
        this.prev = prev;
        this.next = next;
    }
}

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
    this.capacity = capacity;
    this.head = new Node(Infinity, Infinity);
    this.tail = new Node(-Infinity, -Infinity);
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.nodeMap = new Map([
        [this.head.key, this.head],
        [this.tail.key, this.tail],
    ]);
};

/**
 * @param {Node} node
 * @return {void}
 */
LRUCache.prototype.addNode = function (node) {
    node.prev = null;
    node.next = this.head;
    this.head.prev = node;
    this.head = node;
};

/**
 * @param {Node} node
 * @return {void}
 */
LRUCache.prototype.removeNode = function (node) {
    const { prev, next } = node;

    if (prev && next) {
        [prev.next, next.prev] = [next, prev];
    } else if (prev) {
        prev.next = null;
        this.tail = prev;
    } else if (next) {
        next.prev = null;
        this.head = next;
    }
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    const node = this.nodeMap.get(key);

    if (!node) {
        return -1;
    }

    this.removeNode(node);
    this.addNode(node);

    return node.value;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    const node = new Node(key, value);

    if (this.nodeMap.has(key)) {
        this.removeNode(this.nodeMap.get(key));
    }

    this.addNode(node);
    this.nodeMap.set(key, node);
    const n = this.nodeMap.size - this.capacity;

    for (i = 0; i < n; ++i) {
        this.nodeMap.delete(this.tail.key);
        this.removeNode(this.tail);
    }

    return null;
};

Insert Interval

Alkesh Ghorpade — Thu, 08 Jun 2023 13:35:49 +0000

Problem statement

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Problem statement taken from: https://leetcode.com/problems/insert-interval.

Example 1:

Input: intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
Output: [[1, 5], [6, 9]]

Example 2:

Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
Output: [[1, 2], [3, 10], [12, 16]]
Explanation: Because the new interval [4, 8] overlaps with [3, 5], [6, 7], [8, 10].

Constraints:

- 0 <= intervals.length <= 10^4
- intervals[i].length == 2
- 0 <= starti <= endi <= 10^5
- intervals is sorted by starti in ascending order.
- newInterval.length == 2
- 0 <= start <= end <= 10^5

Solutions for Insert Interval

Approach 1: Handle all cases

When working on these kinds of problems, we first consider all the cases we need to handle when inserting a new interval. Here are the five cases we need to handle in our code:

Let's assume the new interval that gets inserted is [a, b].

Case 1: b < start value of first interval in list Insert the interval at the beginning of the list.
Case 2: end value of last interval in list < a Insert the interval at the end of the list
Case 3: a < (start value of first interval) and b > (end value of last interval) The new interval is a superset of this list. It contains all the intervals of the list. We return the new interval as a result.
Case 4: The new interval falls in between any two intervals in the list and is not overlapping with any interval We simply insert the interval in the correct position in the list. For eg.,

   Input: List : [23, 46], [49, 65], [100, 120]
   New interval : [70, 89]
   Output: [23, 46], [49, 65], [70, 89], [100, 120]

Case 5: When new interval overlaps with the intervals of the list We merge the new interval with overlapping intervals. To understand this case, please refer to the previous blog Merge Intervals.

A C++ snippet of this approach is as follows:

vector<vector<int>> insertNewInterval (vector<vector<int>>& intervals, interval newInterval) {
    vector<vector<int>> result;
    int n = intervals.size();

    // if the set is empty, then simply insert newInterval and return.
    if (n == 0) {
        result.push_back(newInterval);
        return result;
    }

    // case 1 and case 2 (new interval is not overlapping with any interval)
    if (newInterval[1] < intervals[0][0] || newInterval[0] > intervals[n - 1][1]) {
        if (newInterval[1] < intervals[0][0])
            result.push_back(newInterval);

        for (int i = 0; i < n; i++)
            result.push_back(intervals[i]);

        if (newInterval[0] > intervals[n - 1][1])
            result.push_back(newInterval);

        return result;
    }

    // case 3 (New interval covers all existing)
    if (newInterval[0] <= intervals[0][0] && newInterval[1] >= intervals[n - 1][1]) {
        result.push_back(newInterval);
        return result;
    }

    // case 4 and case 5
    // Two cases need to check whether intervals overlap or not.
    bool overlap = true;

    for (int i = 0; i < n; i++) {
        overlap = doesOverlap(intervals[i], newInterval);
        if (!overlap) {
            result.push_back(intervals[i]);

            // case 4
            if (i < n && newInterval[0] > intervals[i][1] && newInterval[1] < intervals[i + 1][0])
                result.push_back(newInterval);

            continue;
        }

        // case 5: Merge Overlapping intervals.
        vector<int> temp;
        temp[0] = min(newInterval[0], intervals[i][0]);

        // Traverse the set until intervals are overlapping
        while (i < n && overlap) {
            // ending time of the newly merged interval is the maximum ending time of both
            // overlapping intervals.
            temp[1] = max(newInterval[1], intervals[i][1]);

            if (i == n - 1)
                overlap = false;
            else
                overlap = doesOverlap(intervals[i + 1], newInterval);
            i++;
        }

        i--;
        result.push_back(temp);
    }

    return result;
}

bool doesOverlap(vector<int> a, vector<int> b) {
    return (min(a[1], b[1]) >= max(a[0], b[0]));
}

The time complexity of this approach is O(n), and the space complexity is O(n).

Approach 2: Using Merge Intervals

As mentioned above, we can use the Merge Intervals approach to solve this problem.

We insert the new interval in the list and use the merge intervals solution.

A C++ snippet of this approach is as follows:

vector<vector<int>> merge(vector<vector<int>>& intervals, vector<int> newInterval) {
    intervals.push_back(newInterval);
    sort(intervals.begin(), intervals.end());

    vector<vector<int>> result;

    for(auto interval: intervals){
        if(result.empty() || (result.back()[1] < interval[0])){
            result.push_back({interval[0], interval[1]});
        } else {
            result.back()[1] = max(result.back()[1], interval[1]);
        }
    }

    return result;
}

The time complexity of this approach is O(n * log n), because we are sorting the list. The space complexity is O(1).

Approach 3: Using Stack

We use stack to identify the interval in which it can be merged or placed at the correct position.

The C++ snippet of this approach is as follows:

vector<vector<int>> merge(vector<vector<int>>& intervals, vector<int> newInterval) {
    stack< pair<int, int> > st;

    // push the first interval to stack
    st.push(intervals[0]);

    // store the top element of the stack
    vector<int> top = st.top();

    // Checking is newInterval[0] is less than top[1]
    if (newInterval[0] < top[1]) {
        // pop the top element as it will merge with the
        // previous range
        st.pop();

        // re-assign top[0]
        top[0] = min(top[0], newInterval[0]);

        // re-assign top[1]
        top[1] = max(top[1], newInterval[1]);

        // push the current interval
        st.push(top);
    } else {
       st.push(newInterval);
    }

    // iterate from i = 1 to n - 1
    for (int i = 1; i < n; i++) {
        // store the top element of the stack st
        vector<int> top = st.top();

        // if intervals[i][0] is less than top[1]
        if (intervals[i][0] < top[1]) {
            st.pop();

            // re-assign top[0]
            top[0] = min(top[0], intervals[i][0]);

            // re-assign top[1]
            top[1] = max(top[1], intervals[i][1]);

            // push the current interval
            st.push(top);
        } else {
            st.push(intervals[i]);
        }
    }

    // storing the final intervals
    stack<vector<vector<int>>> result;

    // popping the stack elements
    while (st.empty() != true) {
        vector<int> element = st.top();
        st.pop();

        result.push(element);
    }

    return result;
}

The time complexity of this approach is O(n), and the space complexity is O(n).

Approach 4: Optimized solution without using additional space

We can solve this problem without using any additional space. In Approach 1, we handled five cases. We need to handle only cases 1 and 4 explicitly, and the rest of the cases can be handled in a single loop.

Let's check the algorithm first.

Algorithm

// set size of intervals array
- n = intervals.size()
  i = 0

// iterate over the intervals list till the new interval start value is less than
// any of the interval's end values in the list
- loop while i < n && intervals[i][1] < newInterval[0]

  // keep adding the intervals to the final result
  - result.push_back(intervals[i])

  - increment i; i++
- end while

// once we find the correct slot, now loop till the new interval end value is greater than
// any of the interval's start values in the list
- loop while i < n && newInterval[1] >= intervals[i][0]

  // this code will handle the merging of the intervals based on
  // new interval start and end values
  // we also update the values of the new interval
  - newInterval[0] = min(newInterval[0], intervals[i][0])
  - newInterval[1] = max(newInterval[1], intervals[i][1])

  - increment i; i++
- end while

// append the new interval to result
- result.push_back(newInterval)

// append the remaining intervals of the list to the result
- loop while i < n
  - result.push_back(intervals[i])
  - increment i; i++
- end while

- return result

The time complexity of this approach is O(n), and the space complexity is O(1).

Check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size(), i = 0;
        vector<vector<int>> result;

        while(i < n && intervals[i][1] < newInterval[0]){
            result.push_back(intervals[i]);
            i++;
        }

        while(i < n && newInterval[1] >= intervals[i][0]){
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }

        result.push_back(newInterval);

        while(i < n){
            result.push_back(intervals[i]);
            i++;
        }

        return result;
    }
};

Golang solution

func insert(intervals [][]int, newInterval []int) [][]int {
    n, i := len(intervals), 0
    var result [][]int

    for i < n && intervals[i][1] < newInterval[0] {
        result = append(result, intervals[i])
        i++
    }

    for i < n && newInterval[1] >= intervals[i][0] {
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i++
    }

    result = append(result, newInterval)

    for i < n {
        result = append(result, intervals[i])
        i++
    }

    return result
}

func min(a, b int) int {
    if a < b {
        return a
    }

    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }

    return b
}

JavaScript solution

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function(intervals, newInterval) {
    let n = intervals.length, i = 0;
    let result = [];

    while(i < n && intervals[i][1] < newInterval[0]){
        result.push(intervals[i]);
        i++;
    }

    while(i < n && newInterval[1] >= intervals[i][0]){
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }

    result.push(newInterval);

    while(i < n){
        result.push(intervals[i]);
        i++;
    }

    return result;
};

Dry Run

Let's dry-run our algorithm to see how the solution works.

Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]]
       newInterval = [4, 8]

Step 1: n = intervals.size()
          = 5
        i = 0
        vector<vector<int>> result

Step 2: loop while i < n && intervals[i][1] < newInterval[0]
          0 < 5 && intervals[0][1] < newInterval[0]
          true && 2 < 4
          true

          result.push_back(intervals[i])
          result.push_back(intervals[0])
          result.push_back([1, 2])
          result = [[1, 2]]

          i++
          i = 1

        loop while i < n && intervals[i][1] < newInterval[0]
          1 < 5 && intervals[1][1] < newInterval[0]
          true && 5 < 4
          false

Step 3: loop while i < n && newInterval[1] >= intervals[i][0]
          1 < 5 && newInterval[1] >= intervals[1][0]
          true && 8 >= 3
          true

          newInterval[0] = Math.min(newInterval[0], intervals[i][0])
                         = Math.min(newInterval[0], intervals[1][0])
                         = Math.min(4, 3)
                         = 3

          newInterval[1] = Math.max(newInterval[1], intervals[i][1])
                         = Math.max(newInterval[1], intervals[1][1])
                         = Math.max(8, 5)
                         = 8

          newInterval = [3, 8]

          i++
          i = 2

        loop while i < n && newInterval[1] >= intervals[i][0]
          2 < 5 && newInterval[1] >= intervals[2][0]
          true && 8 >= 6
          true

          newInterval[0] = Math.min(newInterval[0], intervals[i][0])
                         = Math.min(newInterval[0], intervals[1][0])
                         = Math.min(3, 6)
                         = 3

          newInterval[1] = Math.max(newInterval[1], intervals[i][1])
                         = Math.max(newInterval[1], intervals[1][1])
                         = Math.max(8, 7)
                         = 8

          newInterval = [3, 8]

          i++
          i = 3

        loop while i < n && newInterval[1] >= intervals[i][0]
          3 < 5 && newInterval[1] >= intervals[3][0]
          true && 8 >= 8
          true

          newInterval[0] = Math.min(newInterval[0], intervals[i][0])
                         = Math.min(newInterval[0], intervals[3][0])
                         = Math.min(3, 8)
                         = 3

          newInterval[1] = Math.max(newInterval[1], intervals[i][1])
                         = Math.max(newInterval[1], intervals[3][1])
                         = Math.max(8, 10)
                         = 10

          newInterval = [3, 10]

          i++
          i = 4

        loop while i < n && newInterval[1] >= intervals[i][0]
          4 < 5 && newInterval[1] >= intervals[4][0]
          true && 8 >= 12
          false

Step 4: result.push_back(newInterval)
        result.push_back([3, 10])
        result = [[1, 2], [3, 10]]

Step 5: loop while i < n
          4 < 5
          true

          result.push_back(intervals[i])
          result.push_back(intervals[4])
          result.push_back([12, 16])
          result = [[1, 2], [3, 10], [12, 16]]

          i++
          i = 5

        loop while i < n
          5 < 5
          false

Step 6: return result

We return the answer as [[1, 2], [3, 10], [12, 16]].

Kth Largest Element in an Array

Alkesh Ghorpade — Sun, 04 Jun 2023 17:49:25 +0000

Problem statement

Given an integer array nums and an integer k, return the Kth largest element in the array.

Note that it is the Kth largest element in the sorted order, not the Kth distinct element.

You must solve it in O(n) time complexity.

Problem statement taken from: https://leetcode.com/problems/Kth-largest-element-in-an-array.

Example 1:

Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5

Example 2:

Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4

Constraints:

- 1 <= k <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4

Solutions for Kth Largest Element in an Array

Approach 1: Bubble sort

We can use Bubble sort to find the Kth largest element in an array.

We modify the Bubble sort to run the outer loop at most K times.
At the end of the last loop, print the K - 1 th element.

A C++ snippet of this approach is as follows:

// A function to implement bubble sort
void bubbleSort(vector<int>& nums, int n){
    int i, j;

    // run the outer loop k - 1 times
    for (i = 0; i < k; i++)
        for (j = 0; j < n - i - 1; j++)
            if (nums[j] > nums[j + 1])
                swap(nums[j], nums[j + 1]);

    return nums[k - 1];
}

The time complexity of Bubble sort is O(n ^ 2). But in this case, we are running the outer loop k times. The time complexity of this approach is O(n * k).

We are not using additional space, so the space complexity is O(1).

Approach 2: Sorting

The naive approach is to sort the given array in descending order and return the k - 1 index (0 – Based indexing) element.

A C++ snippet of the above approach looks as below:

// C++ code for K largest elements in an array
int findKthLargest(vector<int>& nums, int k) {
    int n = nums.size();

    sort(nums, nums + n, greater<int>());

    return nums[k - 1];
}

The time complexity of this approach is O(n * log(n)) and the space complexity is O(1).

Approach 3: Min-Heap

We create a Min Heap of size K and compare the root of the Min Heap with other elements on the array. If the element is greater than the root, we swap the values and heapify the heap.

We need to execute the following steps to find the Kth largest element in an array:

Build a Min Heap for the first k elements of the array: nums[0] to nums[k - 1].
Iterater over the remaining elements from nums[k] to nums[n - 1].
Compare the array element with the root of the heap.
If the element is greater than the root, heapify the heap else, do nothing.
After the above steps are done, our Min heap has the K largest elements of the array, and the root is the Kth largest element.

A C++ snippet of this approach is as follows:

int swap(int& x, int& y) {
    int temp = x;
    x = y;
    y = temp;
}

// Min Heap Class
class MinHeap {
    int size;
    int* arr;

public:
    MinHeap(int size, int input[]);
    void heapify(int i);
    void buildHeap();
};

MinHeap::MinHeap(int size, int input[]) {
    this->size = size;
    this->arr = input;

    buildHeap();
}

// Min Heapify function, that assumes
// 2 * i + 1 and 2 * i + 2 are min heap and
// fix min heap property for i
void MinHeap::heapify(int i) {
    // if Leaf Node, simply return
    if (i >= size / 2)
        return;

    int smallest;

    // index of left node
    int left = 2 * i + 1;

    // index of right node
    int right = 2 * i + 2;

    // Select minimum from left node and
    // current node i, and store the minimum
    // index in smallest variable
    smallest = arr[left] < arr[i] ? left : i;

    // If right child exist, compare and
    // update the smallest variable
    if (right < size)
        smallest = arr[right] < arr[smallest] ? right : smallest;

    // If Node i violates the min heap
    // property, swap  current node i with
    // smallest to fix the min-heap property
    // and recursively call heapify for node smallest.
    if (smallest != i) {
        swap(arr[i], arr[smallest]);
        heapify(smallest);
    }
}

// Build Min Heap
void MinHeap::buildHeap() {
    // Calling Heapify for all non leaf nodes
    for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(i);
    }
}

int findKthLargest(vector<int>& nums[], int size, int k) {
    // create Min Heap for given array with only k elements
    MinHeap* m = new MinHeap(k, nums);

    // Loop For each element in array
    // after the kth element
    for (int i = k; i < size; i++) {
        // if current element is smaller
        // than minimum element, do nothing
        // and continue to next element
        if (nums[0] > nums[i])
            continue;

        // Otherwise Change minimum element to
        // current element, and call heapify to
        // restore the heap property
        else {
            nums[0] = nums[i];
            m->heapify(0);
        }
    }

    // now min heap contains k maximum elements, print the root element as it is the
    // Kth largest element of the array
    return nums[0];
}

The time complexity of this approach is O(n * log k) and the space complexity is O(k).

Approach 4: Priority Queue

Instead of Min Heap, we can use a Priority queue to get the Kth largest element.

Note: A Priority Queue is implemented as Max Heap by default in C++.

We need to execute the following steps to find the Kth largest element in an array:

Iterate over the array and insert the elements in the priority queue.
If the queue size exceeds k, pop the element from the priority queue.
Once we have iterated over the array, return the top element of the priority queue.

A C++ snippet of this approach is as follows:

int findKthLargest(vector<int>& nums, int k) {
    // initialize priority queue
    priority_queue<int, vector<int>, greater<int>> pq;

    // push all the elements
    for (int i = 0; i < nums.size(); i++) {
        pq.push(nums[i]);

        // if the queue side exceeds k, pop the top element
        if (pq.size() > k) {
            pq.pop();
        }
    }

    // return the top element of the priority queue
    return pq.top();
}

The time complexity of this approach is O(n * log k) and the space complexity is O(k).

Approach 5: Using a Binary Search Tree

We can create a Binary Search Tree from the array elements and get the K largest elements of the array.

We need to execute the following steps:

Create a BST by iterating over the array elements.
Traverse the BST in reverse inorder for K times.
Return the Kth largest element.

A C++ snippet of this approach is as follows:

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

class Tree {
public:
    Node* root = NULL;
    void addNode(int data) {
        Node* newNode = new Node();
        newNode->data = data;

        if (!root) {
            root = newNode;
        } else {
            Node* cur = root;
            while (cur) {
                if (cur->data > data) {
                    if (cur->left) {
                        cur = cur->left;
                    } else {
                        cur->left = newNode;
                        return;
                    }
                } else {
                    if (cur->right) {
                        cur = cur->right;
                    } else {
                        cur->right = newNode;
                        return;
                    }
                }
            }
        }
    }

    void printGreatest(int& K, vector<int>& sol, Node* node) {
        if (!node || K == 0)
            return;

        printGreatest(K, sol, node->right);

        if (K <= 0)
            return;

        sol.push_back(node->data);
        K--;

        printGreatest(K, sol, node->left);
    }
};

int findKthLargest(vector<int>& nums, int k) {
    vector<int> sol;
    Tree tree = new Tree();

    for (int i = 0; i < nums.size(); i++) {
        tree.addNode(nums[i]);
    }

    tree.printGreatest(k, sol, tree.root);

    return sol[k - 1];
}

The time complexity of this approach is O(n * log(n)). The space complexity is O(n).

Approach 6: Using Quick Sort

We can modify the Quick Sort algorithm to find the Kth largest element. Let's check the algorithm directly.

Algorithm

// findKthLargest(vector<int>& nums, int k)
- set n = nums.size()

- if n == 1
  - return nums[0]
- end if

- set l = 0, h = n - 1
  target = n - k

- loop while l <= h
  - set pivot = partition(nums, l, h)

  - if pivot < target
    - set l = pivot + 1
  - else if pivot > target
    - set h = pivot - 1
  - else
    - return nums[pivot]
  - end if
- end while

- return -1

// partition(vector<int> &nums, int l, int h)
- set high = nums[h]
      start = l

- loop for i = l; i < h; i++
  - if nums[i] < high
    - swap(nums[start], nums[i])
    - start++
  - end if
- end for

- swap(nums[start], nums[h])

- return start

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

Check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();

        // if nums size is 1 return the first element
        if (n == 1) {
            return nums[0];
        }

        int l = 0, h = n - 1;

        // set target to n - k
        int target = n - k;

        while (l <= h) {
            // set pivot with the value returned by partition function
            int pivot = partition(nums, l, h);

            // if the pivot is less than the target, search the right side
            if (pivot < target) {
                l = pivot + 1;
            } else if (pivot > target) {
                // if the pivot is greater than the target, search the left side
                h = pivot - 1;
            } else {
                // if the pivot is equal to the target, return nums[pivot]
                return nums[pivot];
            }
        }

        return -1;
    }

    int partition(vector<int> &nums, int l, int h) {
        int high = nums[h];
        int start = l;

        for (int i = l; i < h; i++) {
            // if nums[i] is less than high, then swap nums[start] with nums[i]
            if (nums[i] < high) {
                swap(nums[start], nums[i]);
                start++;
            }
        }

        //swap nums[start] with nums[h]
        swap(nums[start], nums[h]);

        return start;
    }
};

Golang solution

func findKthLargest(nums []int, k int) int {
    n := len(nums)

    // if nums size is 1 return the first element
    if n == 1 {
        return nums[0]
    }

    l, h := 0, n - 1

    // set target to n - k
    target := n - k

    for l <= h {
        // set pivot with the value returned by partition function
        pivot := partition(nums, l, h)

        // if the pivot is less than the target, search the right side
        if pivot < target {
            l = pivot + 1
        } else if pivot > target {
            // if the pivot is greater than the target, search the left side
            h = pivot - 1
        } else {
            // if the pivot is equal to the target, return nums[pivot]
            return nums[pivot]
        }
    }

    return -1
}

func partition(nums []int, l, h int) int {
    high := nums[h]
    start := l

    for i := l; i < h; i++ {
        if nums[i] < high {
            // if nums[i] is less than high, then swap nums[start] with nums[i]
            nums[start], nums[i] = nums[i], nums[start]
            start++
        }
    }

    //swap nums[start] with nums[h]
    nums[start], nums[h] = nums[h], nums[start]

    return start
}

JavaScript solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    let n = nums.length;

    // if nums size is 1 return the first element
    if (n == 1) {
        return nums[0];
    }

    let l = 0, h = n - 1;

    // set target to n - k
    let target = n - k;

    while (l <= h) {
        // set pivot with the value returned by partition function
        let pivot = partition(nums, l, h);

        // if the pivot is less than the target, search the right side
        if (pivot < target) {
            l = pivot + 1;
        } else if (pivot > target) {
            // if the pivot is greater than the target, search the left side
            h = pivot - 1;
        } else {
            // if the pivot is equal to the target, return nums[pivot]
            return nums[pivot];
        }
    }

    return -1;
};

var partition = function(nums, l, h) {
    let high = nums[h];
    let start = l;

    for (let i = l; i < h; i++) {
        // if nums[i] is less than high, then swap nums[start] with nums[i]
        if (nums[i] < high) {
            [nums[start], nums[i]] = [nums[i], nums[start]];
            start++;
        }
    }

    //swap nums[start] with nums[h]
    [nums[start], nums[h]] = [nums[h], nums[start]];

    return start;
}

Dry Run

Let's dry-run our algorithm to see how the solution works.

Input: nums = [3, 2, 1, 5, 6, 4]
       k = 2

// findKthLargest(vector<int>& nums, int k)
Step 1: n = nums.size()
          = 6

Step 2: if n == 0
           6 == 0
           false

Step 3: l = 0
        h = n - 1
          = 6 - 1
          = 5

        target = n - k
               = 6 - 2
               = 4

Step 4: loop while l <= h
          0 <= 5
          true

          pivot = partition(nums, l, h)
                = partition(nums, 0, 5)

// partition(nums, 0, 5)
Step 5: high = nums[h]
             = nums[5]
             = 4
        start = l
              = 0

        loop for i = l; i < h
          i < h
          0 < 5
          true

          if nums[i] < high
            nums[0] < 4
            3 < 4
            true

            swap(nums[start], nums[i])
            swap(nums[0], nums[0])
            nums = [3, 2, 1, 5, 6, 4]

            start++
            start = 1

            i++
            i = 1

        loop for i < h
          i < h
          1 < 5
          true

          if nums[i] < high
            nums[1] < 4
            2 < 4
            true

            swap(nums[start], nums[i])
            swap(nums[1], nums[1])
            nums = [3, 2, 1, 5, 6, 4]

            start++
            start = 2

            i++
            i = 2

        loop for i < h
          i < h
          2 < 5
          true

          if nums[i] < high
            nums[2] < 4
            1 < 4
            true

            swap(nums[start], nums[i])
            swap(nums[2], nums[2])
            nums = [3, 2, 1, 5, 6, 4]

            start++
            start = 3

            i++
            i = 3

        loop for i < h
          i < h
          3 < 5
          true

          if nums[i] < high
            nums[3] < 4
            5 < 4
            false

            i++
            i = 4

        loop for i < h
          i < h
          4 < 5
          true

          if nums[i] < high
            nums[4] < 4
            6 < 4
            false

            i++
            i = 5

        loop for i < h
          i < h
          5 < 5
          false

        swap(nums[start], nums[h])
        swap(nums[3], nums[5])
        swap(5, 4)
        nums = [3, 1, 2, 4, 6, 5]


        return start
        return 3

// findKthLargest(vector<int>& nums, int k)
Step 6: pivot = partition(nums, 0, 5)
              = 3

Step 7: if pivot < target
           3 < 4
           true

           l = pivot + 1
             = 3 + 1
             = 4

Step 8 loop while l <= h
         4 <= 5
         true

         pivot = partition(nums, l, h)
               = partition(nums, 4, 5)

// partition(nums, 4, 5)
Step 9: high = nums[h]
             = nums[5]
             = 5
        start = l
              = 4

        loop for i = l; i < h
          i < h
          4 < 5
          true

          if nums[i] < high
             nums[4] < 5
             6 < 5
             false

          i++
          i = 5

        loop for i < h
          5 < 5
          false

        swap(nums[start], nums[h])
        swap(nums[4], nums[5])
        swap(6, 5)

        nums = [3, 1, 2, 4, 5, 6]

        return start
        return 4

// findKthLargest(vector<int>& nums, int k)
Step 10: pivot = partition(nums, 4, 5)
               = 4

Step 11: if pivot < target
           4 < 4
           false
         else if pivot > target
           4 > 4
           false
         else
           return nums[4]
           return 5

We return the answer as 5.

Word Ladder - LeetCode

Alkesh Ghorpade — Thu, 01 Jun 2023 18:41:23 +0000

Problem statement

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the **number of words* in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.*

Problem statement taken from: https://leetcode.com/problems/word-ladder.

Example 1:

Input: beginWord = 'hit', endWord = 'cog', wordList = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
Output: 5
Explanation: One shortest transformation sequence is 'hit' -> 'hot' -> 'dot' -> 'dog' -> cog', which is 5 words long.

Example 2:

Input: beginWord = 'hit', endWord = 'cog', wordList = ['hot', 'dot', 'dog', 'lot', 'log']
Output: 0
Explanation: The endWord 'cog' is not in wordList, therefore there is no valid transformation sequence.

Constraints:

- 1 <= beginWord.length <= 10
- endWord.length == beginWord.length
- 1 <= wordList.length <= 5000
- wordList[i].length == beginWord.length
- beginWord, endWord, and wordList[i] consist of lowercase English letters
- beginWord != endWord
- All the words in wordList are unique.

Solutions for World Ladder

Approach 1

The idea is to use BFS traversal. Two adjacent words can be considered as nodes of the graph. The count of the number of different characters between the two words can be considered as the distance. If the difference is 1, we return the count. Else we consider every other word in the wordList and check the difference. If the difference is 1, we push the word to the queue.

The algorithmic flow of this approach is as follows:

- i = 1
  q = new Queue()
  q.push(beginWord)
  set count = 1

- initialize set<string> s
  s.insert(begin)

- loop while !q.empty()
  - size = q.size()

  - for i = 0; i < size; i++
    - currentWord = q.first()
    - q.pop()

    - if currentWord == endWord
      - return count
    - end if

    // check stores the count of the number of characters different
    // in the currentWord and endWord
    - check = 0

    - for i = 0; i < currentWord.length; i++
      - if currentWord[i] != endWord[i]
        - count++
      - end if
    - end for

    // if the number of different characters is 1, this means
    // we have reached the endWord and return count
    - if check == 1
      - return count
    - end if

    // add the next word to the queue
    - loop for j = 0; j < wordList.size(); j++
      - set diff = 0

      - loop for k = 0; k < currentWord.size(); k++
        - if currentWord[k] != wordList[j][k]
          - increment diff++
        - end if
      - end for

      - if diff == 1
        - if
      - end if
    - end for
  - end for

- end while

// if we cannot reach the endWord, we return -1
- return -1

The time complexity of this approach is O(n * n * m). Where m is the length of each string. The space complexity is O(n), as we are using an additional space in terms of the queue.

Approach 2

Another approach is to use BFS traversal along with Trie data structure.

The algorithmic flow of this approach is as follows:

- set TrieNode *root =  new TrieNode

- q = new Queue()
  q.push(beginWord)

  // create a hash map of visited node
  unordered_map<string, int> map;

  - for i = 0; i < wordList.size; i++
    - map[wordList[i]] = 0
  - end for

  map[beginWord] = 1

  - loop while !q.empty()
    - currentWord = q.first()
    - q.pop()

    - if currentWord == endWord
      - return map[str]
    - end if

    // initialize allPossible vector
    - vector<string> allPossible

    - allPermutations(root, currentWord, allPossible)

    - loop for string x: allPossible
      - if map.count(x) == 0
        - q.push(x)
        - map[x] = map[str] + 1
      - end if
    - end for
  - end while
-

// allPermutations(root, currentWord, allPossible, currentString = '', changed = false, i = 0)
- if root == NULL
  - return
- end if

- if currentWord.size() == currentString.size()
  - if root -> endOfWord
    - allPossible.push_back(currentString)
    - return
  - end if
- end if

- loop for auto x: root -> children
  - currentString.push_back(x.first)

  - if x.first == currentWord[i]
    - allPermutations(x.second, currentWord, allPossible, currentString, changed, i + 1)
  - else if !changed
    - allPermutations(x.second, currentWord, allPossible, currentString, !changed, i + 1)
  - end if

  // BackTrack.
  currentString.pop_back();
- end for

Both the time and space complexity of this approach is O(n * m * m). Where m is the length of each string.

Approach 3

Another approach to solving this problem via the BFS approach is using a Queue and Set. To find the shortest path, we start from the beginWord and push it into a queue. If the endWord is found, then we return that level of BFS. If we fail to find the endWord in the first iteration, we generate all the words by replacing each character in the string with a till z. When the endWord is found, we return the length of the shortest chain of words.

Algorithm

The algorithmic flow of this approach is as follows:

- create set set<string> s(wordList.begin(), wordList.end())

// If the target endWord is not
// present in the set return 0
- if s.find(endWord) == s.end()
  - return 0
- end if

// initialize queue and push the startWord
- queue<string> q
  q.push(beginWord)

- set result = 0
  initialize i, j, size
  char k
  string currentWord
  int wordLength = beginWord.size()

- loop while !q.empty
  - ++result
  - size = q.size()

  // update the queue while traversing with words
  // that are present in the set
  - loop for i = 0; i < size; i++
    - currentWord = q.front()
    - q.pop()

    // loop to traverse every character of the word
    - loop for j = 0; j < wordLength; j++
      - set char originalChar = currentWord[j]

      // replace the current character in the word
      // with every possible alphabhet
      - loop for k = 'a'; k <= 'z'; k++
        - set currentWord[j] = k

        // if we find the endWord, return result + 1
        - if currentWord == endWord
          - return result + 1
        - end if

        // if the currentWord is not in the set, continue
        // the loop else remove it from the set
        - if s.find(currentWord) == s.end()
          - continue
        - end if

        // push the newly generated word to the queue
        q.push(currentWord)
      - end for

      - currentWord[j] = originalChar
    - end for
  - end for

- end while

- return 0

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

Check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        set<string> s(wordList.begin(), wordList.end());

        // If the target endWord is not
        // present in the set return 0
        if(s.find(endWord) == s.end()) {
            return 0;
        }

        queue<string> q;
        // push the beginWord to queue
        q.push(beginWord);

        int result = 0;
        int i, j, size;
        char k;
        string currentWord;
        int wordLength = beginWord.size();

        // While the queue is non-empty
        while(!q.empty()) {
            ++result;
            size = q.size();

            // update the queue while traversing with words
            // that are present in the set
            for(i = 0; i < size; i++) {
                currentWord = q.front();
                q.pop();

                // loop to traverse every character of the word
                for(j = 0; j < wordLength; j++) {
                    char originalChar = currentWord[j];

                    // replace the current character in the word
                    // with every possible alphabhet
                    for(k = 'a'; k <= 'z'; k++) {
                        currentWord[j] = k;

                        // if we find the endWord, return result + 1
                        if(currentWord == endWord) {
                            return result + 1;
                        }

                        // if the currentWord is not in the set, continue
                        // the loop else remove it from the set
                        if(s.find(currentWord) == s.end()) {
                            continue;
                        }
                        s.erase(currentWord);

                        // push the newly generated word to the queue
                        q.push(currentWord);
                    }

                    currentWord[j] = originalChar;
                }
            }
        }

        return 0;
    }
};

Golang solution

func ladderLength(beginWord string, endWord string, wordList []string) int {
    s := make(map[string]bool)
    for _, word := range wordList {
        s[word] = true
    }

    // If the target endWord is not
    // present in the set return 0
    if _, ok := s[endWord]; !ok {
        return 0
    }

    q := []string{}
    // push the beginWord to queue
    q = append(q, beginWord)

    result := 0
    wordLength := len(beginWord)

    // While the queue is non-empty
    for len(q) > 0 {
        result += 1
        size := len(q)

        // update the queue while traversing with words
        // that are present in the set
        for i := 0; i < size; i++ {
            currentWord := q[0]
            q = q[1:]

            // loop to traverse every character of the word
            for j := 0; j < wordLength; j++ {
                originalChar := currentWord[j]

                // replace the current character in the word
                // with every possible alphabhet
                for k := 'a'; k <= 'z'; k++ {
                    currentWord = replaceAtIndex(currentWord, k, j)

                    // if we find the endWord, return result + 1
                    if currentWord == endWord {
                        return result + 1
                    }

                    // if the currentWord is not in the set, continue
                    // the loop else remove it from the set
                    if _, ok := s[currentWord]; !ok {
                        continue
                    }

                    delete(s, currentWord)

                    // push the newly generated word to the queue
                    q = append(q, currentWord)
                }

                currentWord = replaceAtIndex(currentWord, rune(originalChar), j)
            }
        }
    }

    return 0
}

func replaceAtIndex(in string, r rune, i int) string {
    out := []rune(in)
    out[i] = r
    return string(out)
}

JavaScript solution

/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function(beginWord, endWord, wordList) {
    var s = new Set(wordList);

    // If the target endWord is not
    // present in the set return 0
    if(!s.has(endWord)) {
        return 0;
    }

    // variable q will act as queue
    var q = [];
    // push the beginWord to queue
    q.push(beginWord);

    let result = 0;
    let i, j, size;
    let k;
    let currentWord;
    let wordLength = beginWord.length;

    // While the queue is non-empty
    while(q.length !== 0) {
        ++result;
        size = q.length;

        // update the queue while traversing with words
        // that are present in the set
        for(i = 0; i < size; i++) {
            currentWord = q.shift();

            // loop to traverse every character of the word
            for(j = 0; j < wordLength; j++) {
                let originalChar = currentWord[j];

                // replace the current character in the word
                // with every possible alphabhet
                for(k = 97; k <= 122; k++) {
                    currentWord = currentWord.substring(0, j) + String.fromCharCode(k) + currentWord.substring(j + 1);

                    // if we find the endWord, return result + 1
                    if(currentWord === endWord) {
                        return result + 1;
                    }

                    // if the currentWord is not in the set, continue
                    // the loop else remove it from the set
                    if(!s.has(currentWord)) {
                        continue;
                    }
                    s.delete(currentWord);

                    // push the newly generated word to the queue
                    q.push(currentWord);
                }

                currentWord = currentWord.substring(0, j) + originalChar + currentWord.substring(j + 1);
            }
        }
    }

    return 0;
};

Dry Run

Let's dry-run our algorithm to see how the solution works.

Input: beginWord = 'hit', endWord = 'cog', wordList = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']

Step 1: set<string> s(wordList.begin(), wordList.end())
        s = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']

Step 2: if s.find(endWord) == s.end()
           s.find('cog') == s.end()
           false

Step 3: queue<string> q
        q = []
        q.push(startWord)
        q = ['hit']

        int result = 0
        int i, j, size
        char k
        string currentWord
        wordLength = beginWord.size()
                   = 'hit'.size()
                   = 3

Step 4: loop while !q.empty()
          q = ['hit']
          q.empty() = false
          !q.empty()
          true

          ++result
          result = 1

          size = q.size()
               = 1

          loop for i = 0; i < size;
            i < size
            0 < 1
            true

            currentWord = q.front()
                        = 'hit'

            q.pop()
            q = []

            loop for j = 0; j < wordLength
              j < wordLength
              0 < 3
              true

              originalChar = currentWord[j]
                           = 'hit'[0]
                           = 'h'

              loop for k = 'a'; k <= 'z';
                a <= 'z'
                true

                currentWord[j] = k
                currentWord[0] = 'a'
                currentWord = 'ait'

                if currentWord == endWord
                   'ait' == 'cog'
                   false

                if s.find(currentWord) == s.end()
                   s.find('ait') == s.end()
                   // as the set s does not include 'ait' so the condition is true
                   s = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
                   true

                   continue

                k++

                k = 'b'

                the loop continues till 'z' as we don't have any word
                'bit', 'cit',...'hit'...'zit' in the list.

            currentWord[j] = originalChar
            currentWord[0] = 'h'
            currentWord = 'hit'

            j++
            j = 1

            loop for j < wordLength
              j < wordLength
              1 < 3
              true

              originalChar = currentWord[j]
                           = 'hit'[1]
                           = 'i'

              loop for k = 'a'; k <= 'z';
                a <= 'z'
                true

                currentWord[j] = k
                currentWord[1] = 'a'
                currentWord = 'hat'

                if currentWord == endWord
                   'hat' == 'cog'
                   false

                if s.find(currentWord) == s.end()
                   s.find('hat') == s.end()
                   // as the set s does not include 'hat' so the condition is true
                   s = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
                   true

                   continue

                k++

                k = 'b'

                the loop continues till 'n' as we don't have any word
                'hbt', 'hct', 'hdt'..'hnt' in the list.

                when k = 'o'
                we get 'hot'

                currentWord[j] = k
                currentWord[1] = 'o'
                currentWord = 'hot'

                if currentWord == endWord
                   'hot' == 'cog'
                   false

                if s.find(currentWord) == s.end()
                   s.find('hot') == s.end()
                   // as the set s does include 'hot' so the condition is false
                   s = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
                   false

                s.erase(currentWord)
                s.erase('hot')
                s = ['dot', 'dog', 'lot', 'log', 'cog']

                q.push(currentWord)
                q.push('hot')
                q = ['hot']

                The loop continues till k is equal to `z` and the loop repeats.

The sequence we follow goes like
'hit' -> 'hot' -> 'dot' -> 'dog' -> 'cog'

We return the result as 5.

Longest Valid Parentheses - LeetCode

Alkesh Ghorpade — Sun, 28 May 2023 09:22:12 +0000

Problem statement

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

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

Example 1:

Input: s = '(()'
Output: 2
Explanation: The longest valid parentheses substring is '()'.

Example 2:

Input: s = ')()())'
Output: 4
Explanation: The longest valid parentheses substring is '()()'.

Example 3:

Input: s = ''
Output: 0

Constraints:

- 0 <= s.length <= 3 * 10^4
- s[i] is '(', or ')'

Solutions for Longest Valid Parentheses

Approach 1: Brute Force

The brute force approach is to generate all the substrings and check whether every string is valid parentheses. If the substring is valid and the length exceeds the maximum length seen so far, then update the maximum length. We return this maximum length as the longest valid parentheses.

The problem with this approach is the time complexity which is O(n^3). Three nested for loops will be used. The first two will generate all the substrings, and the third inner loop will verify whether the substring is valid parentheses.

Approach 2: Using Stack

An efficient way to solve the longest valid parentheses is using a Stack. The solution is similar to our approach in valid parentheses problem. Instead of pushing the open brackets ( to the stack, we push the indexes of the opening brackets.

The algorithm for this approach is as follows:

- initialize stack<int> st
  // push -1 to the stack to provide the base
  // for the next valid set of parentheses
  st.push(-1)

- set result = 0

- loop for i = 0; i < str.size(); i++
  // if opening bracket, push the index i

  - if str[i] == '('
    - st.push(i)

  - else
    // if str[i] == ')'

    // pop the last encountered opening bracket's index
    - if !st.empty()
      - st.pop()
    - end if

    // if the length formed with the base of the current valid substring
    // is more than max so far
    - if !st.empty
      - set result = max(result, i - st.top())
    - else
      - st.push(i)
    - end if
  - end if
- end for

- return result

A C++ snippet of this algorithm is as below:

int longestValidParentheses(string s) {
    stack<int> stk;
    stk.push(-1);

    int result = 0;

    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            stk.push(i);
        } else {
            if (!stk.empty()) {
                stk.pop();
            }

            if (!stk.empty()) {
                result = max(result, i - stk.top());
            } else {
                stk.push(i);
            }
        }
    }

    return result;
}

The time complexity of this approach is O(n) because we are iterating over the string once. The space complexity is also O(n), as we used an additional data structure, Stack.

Approach 3: Using left and right counters

Using two counters, we can solve this problem in O(1) time.

The idea is to scan the string from left to right.
We keep track of the number of open and closed braces using left and right counters. We increment the left and right counter by 1 when identifying an opening ( and closing ) braces.
When the left and right counters are equal, the length of the current substring is calculated. If it exceeds the previous longest valid parentheses, we update the result with the current substring length.
At any point while scanning, if the right counter value exceeds the left counter, the substring is not a valid parentheses string. We set the left and right counters to 0.
We then scan the string from right to left and repeat similar steps above.

Let's check the algorithm for this approach.

Algorithm

- set left, right, maxLength = 0
      n = s.length

- loop for i = 0; i < n; i++
  - if s[i] == '('
    - increment left: left++
  - else
    - increment right: right++
  - end if

  - if left == right
    - update maxLength: maxLength = max(maxLength, 2 * right)
  - else if right > left
    - set left, right = 0, 0
  - end if
- end for

- set left, right = 0, 0

- loop for i = 0; i < n; i++
  - if s[i] == '('
    - increment left: left++
  - else
    - increment right: right++
  - end if

  - if left == right
    - update maxLength: maxLength = max(maxLength, 2 * right)
  - else if left > right
    - set left, right = 0, 0
  - end if
- end for

- return maxLength

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

Check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    // Main function to return the length of
    // the longest valid parentheses
    int longestValidParentheses(string s) {
        int left = 0, right = 0, maxLength = 0;
        int n = s.length();

        // iterate the string from left to right
        for(int i = 0; i < n; i++) {
            if(s[i] == '(') {
                left++;
            } else {
                right++;
            }

            // if left is equal to right, we found a
            // valid parentheses substring
            if(left == right) {
                maxLength = max(maxLength, 2 * right);
            } else if (right > left) {
                // reset the left and right counter when we have
                // invalid parentheses substring
                left = 0;
                right = 0;
            }
        }

        left = 0;
        right = 0;

        // iterate the string from right to left
        for(int i = n - 1; i >= 0; i--) {
            if(s[i] == '(') {
                left++;
            } else {
                right++;
            }

            // if left is equal to right, we found a
            // valid parentheses substring
            if(left == right) {
                maxLength = max(maxLength, 2 * right);
            } else if (left > right) {
                // reset the left and right counter when we have
                // invalid parentheses substring
                left = 0;
                right = 0;
            }
        }

        return maxLength;
    }
};

Golang solution

// Main function to return the length of
// the longest valid parentheses
func longestValidParentheses(s string) int {
    left, right, maxLength := 0, 0, 0
    n := len(s)

    // iterate the string from left to right
    for  i := 0; i < n; i++ {
        if s[i] == '(' {
            left++
        } else {
            right++
        }

        // if left is equal to right, we found a
        // valid parentheses substring
        if left == right {
            maxLength = max(maxLength, 2 * right)
        } else if (right > left) {
            // reset the left and right counter when we have
            // invalid parentheses substring
            left = 0
            right = 0
        }
    }

    left = 0
    right = 0

    // iterate the string from right to left
    for i := n - 1; i >= 0; i-- {
        if s[i] == '(' {
            left++
        } else {
            right++
        }

        // if left is equal to right, we found a
        // valid parentheses substring
        if left == right {
            maxLength = max(maxLength, 2 * right)
        } else if (left > right) {
            // reset the left and right counter when we have
            // invalid parentheses substring
            left = 0
            right = 0
        }
    }

    return maxLength
}

func max(a, b int) int {
    if a > b {
        return a
    }

    return b
}

JavaScript solution

// Main function to return the length of
// the longest valid parentheses
var longestValidParentheses = function(s) {
    let left = 0, right = 0, maxLength = 0;
    let n = s.length;

    // iterate the string from left to right
    for(let i = 0; i < n; i++) {
        if(s[i] == '(') {
            left++;
        } else {
            right++;
        }

        // if left is equal to right, we found a
        // valid parentheses substring
        if(left == right) {
            maxLength = Math.max(maxLength, 2 * right);
        } else if (right > left) {
            // reset the left and right counter when we have
            // invalid parentheses substring
            left = 0;
            right = 0;
        }
    }

    left = 0;
    right = 0;

    // iterate the string from right to left
    for(let i = n - 1; i >= 0; i--) {
        if(s[i] == '(') {
            left++;
        } else {
            right++;
        }

        // if left is equal to right, we found a
        // valid parentheses substring
        if(left == right) {
            maxLength = Math.max(maxLength, 2 * right);
        } else if (left > right) {
            // reset the left and right counter when we have
            // invalid parentheses substring
            left = 0;
            right = 0;
        }
    }

    return maxLength;
};

Dry Run

Let's dry-run our algorithm to see how the solution works.

Input: s = ')()())'

Step 1: set left = 0, right = 0, maxLength = 0
        n = s.size()
          = 6

Step 2: loop for i = 0; i < n
          0 < 6
          true

          if s[i] == '('
             s[0] == '('
             ')' == '('
             false
          else
            right++
            right = 1

          if left == right
            0 == 1
            false
          else if right > left
            1 > 0
            true

            left = 0
            right = 0

          i++
          i = 1

Step 3: loop for i < n
          1 < 6
          true

          if s[i] == '('
            s[1] == '('
            '(' == '('
            true
            left++
            left = 1

          if left == right
            1 == 0
            false
          else if right > left
            0 > 1
            false

          i++
          i = 2

Step 4: loop for i < n
          2 < 6
          true

          if s[i] == '('
             s[2] == '('
             ')' == '('
             false
          else
            right++
            right = 1

          if left == right
            1 == 1
            true

            maxLength = max(maxLength, 2 * right)
                      = max(0, 2 * 1)
                      = max(0, 2)
                      = 2

          i++
          i = 3

Step 5: loop for i < n
          3 < 6
          true

          if s[i] == '('
            s[3] == '('
            '(' == '('
            true
            left++
            left = 2

          if left == right
            2 == 1
            false
          else if right > left
            1 > 2
            false

          i++
          i = 4

Step 6: loop for i < n
          4 < 6
          true

          if s[i] == '('
             s[4] == '('
             ')' == '('
             false
          else
            right++
            right = 2

          if left == right
            2 == 2
            true

            maxLength = max(maxLength, 2 * right)
                      = max(2, 2 * 2)
                      = max(2, 4)
                      = 4

          i++
          i = 5

Step 7: loop for i < n
          5 < 6
          true

          if s[i] == '('
            s[5] == '('
            ')' == '('
            false
          else
            right++
            right = 3

          if left == right
            2 == 3
            false
          else
            left = 0
            right = 0

          i++
          i = 6

Step 8: loop for i < n
          6 < 6
          false

Step 9: left = 0
        right = 0

Step 10: loop for i = n - 1; i >= 0
           i = 6 - 1 = 5
           i >= 0
           5 >= 0
           true

           if s[i] == '('
             s[5] == '('
             ')' == '('
             false
           else
             right++
             right = 1

           if left == right
             0 == 1
             false
           else if left > right
             0 > 1
             false

           i--
           i = 4

Step 11: loop for i >= 0
           4 >= 0
           true

           if s[i] == '('
             s[4] == '('
             ')' == '('
             false
           else
             right++
             right = 2

           if left == right
             0 == 2
             false
           else if left > right
             0 > 2
             false

           i--
           i = 3

Step 12: loop for i >= 0
           3 >= 0
           true

           if s[i] == '('
             s[3] == '('
             '(' == '('
             true
             left++
             left = 1

           if left == right
             1 == 2
             false
           else if left > right
             1 > 2
             false

          i--
          i = 2

Step 13: loop for i >= 0
           2 >= 0
           true

           if s[i] == '('
             s[2] == '('
             ')' == '('
             false
           else
             right++
             right = 3

           if left == right
             1 == 3
             false
           else if left > right
             1 > 3
             false

           i--
           i = 1

Step 14: loop for i >= 0
           1 >= 0
           true

           if s[i] == '('
             s[1] == '('
             '(' == '('
             true
             left++
             left = 2

           if left == right
             2 == 3
             false
           else if left > right
             2 > 3
             false

           i--
           i = 0

Step 15: loop for i >= 0
           0 >= 0
           true

           if s[i] == '('
             s[1] == '('
             ')' == '('
             false
           else
             right++
             right = 4

           if left == right
             2 == 4
             false
           else if left > right
             2 > 4
             false

           i--
           i = -1

Step 16: loop for i >= 0
           -1 >= 0
           false

Step 17: return maxLength

We return the answer as 4.

Merge k Sorted Lists - LeetCode

Alkesh Ghorpade — Sun, 21 May 2023 12:30:22 +0000

Problem statement

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

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

Example 1:

Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] is sorted in ascending order.
- The sum of lists[i].length will not exceed 10^4.

Solutions for Merge k Sorted Lists Problem

Approach 1: Brute Force

In one of the previous blog posts, we discussed how to Sort a single Linked List. In this problem we need to merge K sorted Linked list.

A simple solution would be to connect all k linked lists into one list (in any order). Then use the merge sort algorithm discussed in Sort List post. The worst-case time complexity of this approach is O(n * log(n)), where n is the total number of nodes present in all the k lists. This approach is inefficient as we are not taking advantage of the already sorted lists.

Let's check the C++ snippet of this approach below:

ListNode* getLastNode(ListNode* head) {
    ListNode* current = head;
    ListNode* next = current->next;

    while(next != NULL) {
        current = next;
        next = current->next;
    }

    return current;
}

// Merge k sorted lists: main function
ListNode* mergeKSortedLists(vector<ListNode*>& lists) {
    if(lists.size() == 0) {
        return NULL;
    }

    // connect all k sorted linked lists into one list
    for(int i = 0; i < lists.size() - 1; i++) {
        // fetch the last node
        ListNode* last = getLastNode(lists[i]);

        last->next = lists[i + 1];
    }

    // perform merge sort on list[0]
    return sortList(lists[0]);
}

// merge sort the two list
ListNode* mergelist(ListNode *l1, ListNode *l2) {
    ListNode *ptr = new ListNode(0);
    ListNode *current = ptr;

    while(l1 != NULL && l2 != NULL) {
        if(l1->val <= l2->val) {
            current->next = l1;
            l1 = l1->next;
        } else {
            current->next = l2;
            l2 = l2->next;
        }

        current = current->next;
    }


    if(l1 != NULL) {
        current->next = l1;
        l1 = l1->next;
    }

    if(l2 != NULL) {
        current->next = l2;
        l2 = l2->next;
    }

    return ptr->next;
}

ListNode* sortList(ListNode* head) {
    if(head == NULL || head->next == NULL)
        return head;

    ListNode *temp = NULL;
    ListNode *slow = head;
    ListNode *fast = head;

    // split the list into two halves
    while(fast != NULL && fast->next != NULL) {
        temp = slow;
        slow = slow->next;
        fast = fast->next->next;
    }

    temp->next = NULL;

    // recursively call the sortList function for the two lists
    ListNode* l1 = sortList(head);
    ListNode* l2 = sortList(slow);

    // merge list l1 and l2
    return mergelist(l1, l2);
}

A second brute-force approach to solve the problem is by merging two sorted lists at a time. We merge the first two lists lists[0] with lists[1] and store the result. We merge the result with the third list lists[2] and repeat the process k - 1 time.

This method is relatively easy. But the time complexity of this approach is O(n * k), where n is the number of elements to be merged.

A C++ snippet of this approach is as below:

// Merge k sorted lists: main function
ListNode* mergeKSortedLists(vector<ListNode*>& lists) {
    if(lists.size() == 0) {
        return NULL;
    }

    return mergeKSortedListsHelper(lists);
}

// Helper function to merge k sorted lists
ListNode* mergeKSortedListsHelper(vector<ListNode*>& lists) {
    int size = lists.size();

    // Traverse from the second list to last
    for (int i = 1; i <= size; i++) {
        while(true) {
            ListNode head1 = lists[0], head2 = lists[i];

            // if the list has ended
            if(head1 == NULL) {
                break;
            }

            if(head1->val >= head2->val) {
                lists[i] = head2->next;
                head2->next = head1;
                lists[0] = head2;
            } else {
                // Traverse the first list
                while (head1->next != NULL) {
                    // find the node in the first list which is just
                    // greater than second list current node
                    if (head1->next->val >= head2->val) {
                        lists[i] = head2->next;
                        head2->next = head1->next;
                        head1->next = head2;
                        break;
                    }

                    head1 = head1->next;
                }

                if(head1->next == NULL) {
                    lists[i] = head2->next;
                    head2->next = NULL;
                    head1->next = head2;
                    head1->next->next = NULL;
                    break;
                }
            }
        }
    }

    return lists[0];
}

The time complexity of the above two approaches is very high, as we are not taking advantage of the sorted lists. We can optimize the approach using an additional data structure: Min Heap.

Approach 2: Using Min Heap

We can optimize the above approach by using a Min Heap. The root of the Min Heap is always the smallest element.

As per the problem statement, all the linked lists are sorted. Therefore, the first element of the list will be the smallest. We add the first elements of all the linked lists into a Min Heap. We extract the smallest element, the Min Heap's root. After the root is removed, we increment the pointer of the list to which the root element belonged. The next node of this list is added to the Min Heap. We continue removing the root, and keep adding the next node from the lists to the heap until all the lists are traversed, and the heap is empty.

This algorithm can also be used to merge K sorted arrays. The time complexity of the algorithm is O(n * log(k)). Where n is the number of elements across all the lists and k is the number of linked lists. The space complexity is O(k) where k is the size of the Min Heap.

Let's check the algorithm for this approach.

- priority_queue<ListNode*, vector<ListNode*>, compare> pq

- for int i = 0; i < k; i++
  - if lists[i] != NULL
    - pq.push(arr[i])
  - if end
- for end

- if pq.empty()
  - return NULL
- if end

- ListNode* result = new ListNode(0)
  ListNode* last = dummp

- loop while !pq.empty()
  - ListNode* current = pq.top()
    pq.pop()

  - last->next = current
    last = last->next

  - if current->next != NULL
      pq.push(curr->next)
  - if end
- while end

- return result->next

Let's check the algorithm in C++ code.

ListNode* mergeKSortedLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, compare> pq;
    int k = lists.size();

    // Push the first nodes of all the k lists in priority_queue 'pq'
    for (int i = 0; i < k; i++)
        if (lists[i] != NULL)
            pq.push(lists[i]);

    if (pq.empty())
        return NULL;

    ListNode *result = new ListNode(0);
    ListNode *last = result;

    // Loop till 'pq' is not empty
    while (!pq.empty()) {
        // Get the top element of 'pq'
        ListNode* current = pq.top();
        pq.pop();

        // Add the top element of 'pq' to the result list
        last->next = current;
        last = last->next;

        // If the current next node is not NULL, add it to the priority queue
        if (current->next != NULL) {
            pq.push(curr->next);
        }
    }

    // return the result
    return result->next;
}

Approach 3: Using Divide and Conquer

Using Min Heap, we reduced the time complexity to O(n * log(k)), but it takes O(k) extra space for the heap. We can solve this problem in constant space using Divide and Conquer technique.

As mentioned in our Brute force approach, we know how to merge two sorted lists. The idea is to pair up k lists and merge each pair in linear time using the O(1) space. After the first iteration, k/2 lists of size 2 * n are left. After the second cycle, k/4 lists are left. We repeat the procedure until we have one list left.

Let's check the algorithm first.

// function mergeKLists(vector<ListNode*>& lists)
- if lists.size() == 0
  - return NULL
- if end

- return mergeKListsHelper(lists, lists.size() - 1)

// function mergeKListsHelper(vector<ListNode*>& lists, int last)
// Merge lists until one list is left
- loop while last != 0
  - initilaize i = 0, j = last

  - loop while i < j
    // merge list i with list j
    // store the merged result in list i
    - lists[i] = mergeLists(lists[i], lists[j])

    - increment i = i++
    - decrement j = j--

    - if i >= j
      - last = j
    - if end
  - while end
- while end

- return lists[0]

// function mergeLists(ListNode* l1, ListNode* l2)
- set ListNode* head = NULL

- if l1 == NULL
  - return l2
- else if l2 == NULL
  - return l1
- if end

- if l1->val < l2->val
  - set head = l1
  - set l1 = l1->next
- else
  - set head = l2
  - set l2 = l2->next
- if end

- set ListNode* p = head

- loop while l1 && l2
  - if l1->val < l2->val
    - set p->next = l1
    - set l1 = l1->next
  - else
    - set p->next = l2
    - set l2 = l2->next
  - if end

  - set p = p->next
- while end

- if l1 != NULL
  - p->next = l1
- else
  - p->next = l2
- if end

- return head

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

Let's check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) {
            return NULL;
        }

        return mergeKListsHelper(lists, lists.size() - 1);
    }

    ListNode* mergeKListsHelper(vector<ListNode*>& lists, int last) {
        // Merge lists until one list is left
        while(last != 0) {
            int i = 0, j = last;

            while(i < j) {
                // merge list i with list j
                // store the merged result in list i
                lists[i] = mergeLists(lists[i], lists[j]);

                i++;
                j--;

                // update last when all pairs are merged
                if(i >= j) {
                    last = j;
                }
            }
        }

        return lists[0];
    }

    ListNode* mergeLists(ListNode* l1, ListNode* l2) {
        ListNode* head = NULL;

        // if any one of the two lists is empty
        // return the other list.
        if(l1 == NULL) {
            return l2;
        } else if(l2 == NULL) {
            return l1;
        }

        // choose the head based on the smallest value of two lists.
        if(l1->val < l2->val){
            head = l1;
            l1 = l1->next;
        } else {
            head = l2;
            l2 = l2->next;
        }

        ListNode *p;
        p = head;

        while(l1 && l2){
            if(l1->val < l2->val){
                p->next = l1;
                l1 = l1->next;
            } else {
                p->next = l2;
                l2 = l2->next;
            }

            p = p->next;
        }

        if(l1 != NULL){
            p->next = l1;
        } else {
            p->next = l2;
        }

        return head;
    }
};

Golang solution

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil;
    }

    return mergeKListsHelper(lists, len(lists) - 1)
}

func mergeKListsHelper(lists []*ListNode, last int) *ListNode {
    // Merge lists until one list is left
    for last != 0 {
        i, j := 0, last

        for(i < j) {
            // merge list i with list j
            // store the merged result in list i
            lists[i] = mergeLists(lists[i], lists[j])

            i++;
            j--;

            // update last when all pairs are merged
            if i >= j {
                last = j
            }
        }
    }

    return lists[0]
}

func mergeLists(l1, l2 *ListNode) *ListNode {
    var head *ListNode
    head = nil

    // if any one of the two lists is empty
    // return the other list.
    if l1 == nil {
        return l2
    } else if l2 == nil {
        return l1
    }

    // choose the head based on the smallest value of the two lists.
    if(l1.Val < l2.Val){
        head = l1;
        l1 = l1.Next;
    } else {
        head = l2;
        l2 = l2.Next;
    }

    p := head

    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            p.Next = l1
            l1 = l1.Next
        } else {
            p.Next = l2
            l2 = l2.Next
        }

        p = p.Next
    }

    if l1 != nil {
        p.Next = l1
    } else {
        p.Next = l2
    }

    return head
}

JavaScript solution

var mergeKLists = function(lists) {
    if(lists.length === 0) {
        return null;
    }

    return mergeKListsHelper(lists, lists.length - 1);
};

var mergeKListsHelper = function(lists, last) {
    // Merge lists until one list is left
    while(last != 0) {
        let i = 0, j = last;

        while(i < j) {
            // merge list i with list j
            // store the merged result in list i
            lists[i] = mergeLists(lists[i], lists[j]);

            i++;
            j--;

            // update last when all pairs are merged
            if(i >= j) {
                last = j;
            }
        }
    }

    return lists[0];
};

var mergeLists = function(l1, l2) {
    let head = null;

    // if any one of the two lists is empty
    // return the other list.
    if(l1 == null) {
        return l2;
    } else if(l2 == null) {
        return l1;
    }

    // choose the head based on the smallest value of the two lists.
    if(l1.val < l2.val){
        head = l1;
        l1 = l1.next;
    } else {
        head = l2;
        l2 = l2.next;
    }

    let p = head;

    while(l1 && l2){
        if(l1.val < l2.val){
            p.next = l1;
            l1 = l1.next;
        } else {
            p.next = l2;
            l2 = l2.next;
        }

        p = p.next;
    }

    if(l1 != null){
        p.next = l1;
    } else {
        p.next = l2;
    }

    return head;
};

Let's dry-run our algorithm to see how the solution works.

Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]

// mergeKLists function
Step 1: if lists.size() == 0
          3 == 0
          false

Step 2: return mergeKListsHelper(lists, lists.size() - 1)
               mergeKListsHelper(lists, 2)

// mergeKListsHelper
Step 3: loop while last != 0
          2 != 0
          true

          i = 0
          j = last
            = 2

          loop while i < j
            0 < 2
            true

            lists[i] = mergeLists(lists[i], lists[j])
            lists[0] = mergeLists(lists[0], lists[2])
                     = mergeLists([1, 4, 5], [2, 6])

// mergeLists([1, 4, 5], [2, 6])
Step 4: This function will merge the list and return
        [1, 2, 4, 5, 6]

// mergeKListsHelper
Step 5: i++
        i = 1

        j--
        j = 1

        if i >= j
           1 >= 1
           true

           last = j
           last = 1

        loop while i < j
          1 < 1
          false

// mergeKListsHelper
Step 6: loop while last != 0
          1 != 0
          true

          i = 0
          j = last
            = 1

          loop while i < j
            0 < 1
            true

            lists[i] = mergeLists(lists[i], lists[j])
            lists[0] = mergeLists(lists[0], lists[1])
                     = mergeLists([1, 2, 4, 5, 6], [1, 3, 4])

// mergeLists([1, 2, 4, 5, 6], [1, 3, 4])
Step 7: This function will merge the list and return
        [1, 1, 2, 3, 4, 4, 5, 6]

// mergeKListsHelper
Step 8: i++
        i = 1

        j--
        j = 0

        if i >= j
           1 >= 0
           true

           last = j
           last = 0

        loop while i < j
          1 < 0
          false

Step 9: loop while last != 0
          0 != 0
          false

Step 10: return lists[0]
         [1, 1, 2, 3, 4, 4, 5, 6]

LeetCode - Edit Distance

Alkesh Ghorpade — Sun, 14 May 2023 17:51:31 +0000

Problem statement

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a character
Delete a character
Replace a character

Problem statement taken from: https://leetcode.com/problems/edit-distance

Example 1:

Input: word1 = 'horse', word2 = 'ros'
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = 'intention', word2 = 'execution'
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Constraints:

- 0 <= word1.length, word2.length <= 500
- word1 and word2 consist of lowercase English letters.

Explanation

As per Wikipedia:

Edit Distance is a string metric, i.e. a way of quantifying how dissimilar two strings (e.g., words) are to one another, that is measured by counting the minimum number of operations required to transform one string into the other.

Edit distances find applications in natural language processing, where automatic spelling correction can determine candidate corrections for a misspelled word by selecting words from a dictionary that have a low distance to the word in question. In bioinformatics, it can be used to quantify the similarity of DNA sequences, which can be viewed as strings of the letters A, C, G, and T.

Different definitions of an edit distance use different sets of string operations. Levenshtein distance operations are the removal, insertion, or substitution of a character in the string. Being the most common metric, the term Levenshtein distance is often used interchangeably with edit distance.

In this blog post, we will discuss three solutions to the Edit distance problem. We will start with brute force and try to optimize the solution using Dynamic programming.

Brute Force Approach

The brute approach is based on recursion. We think about the smaller subproblems which can be solved easily. We recurse over the input sequence and figure out which operation Insert, Delete, or Replace will cost the minimum.

We consider i and j as pointers to word1 and word2 respectively. If the first character of both strings are the same we then recurse for lengths i + 1 and j + 1. If the characters are different, we will perform all three operations on that character. We compute which operation cost is minimum.

A C++ snippet of this approach is as follows:

int editDistance(string word1, string word2) {
    if (word1.length() == 0)
        return word2.length();

    if (word2.length() == 0)
        return word1.length();

    return match(word1, word2, 0, 0);
}

int match(string s1, string s2, int i, int j) {
    if (s1.length() == i)
         return s2.length() - j;

    if (s2.length() == j)
        return s1.length() - i;

    int result;

    if (s1[i] == s2[j]) {
        result = match(s1, s2, i + 1, j + 1);
    } else {
        int insertChar = match(s1, s2, i, j + 1);
        int deleteChar = match(s1, s2, i + 1, j);
        int substituteChar = match(s1, s2, i + 1, j + 1);
        result = min(insertChar, deleteChar, substituteChar) + 1;
    }

    return result
}

The time-complexity of this approach is O(3^n). The space-complexity is O(m), where m is the stack space of the recursion tree.

Dynamic Programming: Memoization Approach

If we look at the recursion stack in the brute force approach, we will find many subproblems are overlapping. When we calculate the minimum value for the ith and jth index of word1 and word2 respectively, we store the value in a cache array so that it could be used when needed.

Assuming we know the edit distance of two strings till i and j indices. We can then write

editDistance(i + 1, j + 1) = 1 + min (editDistance(i, j + 1), editDistance(i + 1, j), editDistance(i, j))

We check if the characters at word1[i] is equal to word2[j] then look for cache[i + 1][j + 1].
Else, we take minimum of cache[i + 1][j], cache[i][j + 1], cache[i][j] and add 1 to it and store the result in cache[i + 1][j + 1].

A C++ snippet of this approach is as follows:

int editDistance(string word1, string word2) {
    int cache[word1.length][word2.length];

    for (int i = 0; i < word1.length; i++) {
        for (int j = 0; j < word2.length; j++) {
            cache[i][j] = -1;
        }
    }

    return match(word1, word2, 0, 0, cache);
}

int match(string s1, string s2, int i, int j, int[][] cache){
    if (s1.size() == i)
        return s2.size() - j;

    if (s2.size() == j)
        return s1.size() - i;

    if (cache[i][j] != -1) {
        return cache[i][j];
    }

    if (s1[i] == s2[j]) {
        cache[i][j] = match(s1, s2, i + 1, j + 1, cache);
    } else {
        int insertChar = match(s1, s2, i, j + 1, cache);
        int deleteChar = match(s1, s2, i + 1, j, cache);
        int replaceChar = match(s1, s2, i + 1, j + 1, cache);
        cache[i][j] = min(insertChar, deleteChar, replaceChar) + 1;
    }

    return cache[i][j];
}

The time-complexity of this approach is O(n^2). The space-complexity is O(n^2).

Dynamic Programming: Tabulation Approach

The tabulation approach works in a bottom-up fashion as compared to the top-down Memoization approach. With the bottom-up approach, while calculating editDistance for i and j, we first calculate the minimum from

editDistance(i - 1, j)
editDistance(i, j - 1)
editDistance(i - 1, j - 1)

Let's check the algorithm to understand it clearly.

Algorithm

- set m = word1.length()
      n = word2.length()

- initialize vector<vector<int>> dp(m + 1, vector<int>(n + 1))

- loop for i = 0; i <= m; i++
  - set dp[i][0] = i
- for end

- loop for j = 0; j <= n; j++
  - set dp[0][j] = j
- for end

- loop for i = 1; i <= m; i++
  - loop for j = 1; j <= n; j++
    - if word1[i - 1] == word2[j - 1]
      - set dp[i][j] = dp[i - 1][j - 1]
    - else
      - set dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
    - if end
  - for end
- for end

- return dp[m][n]

The time-complexity of this approach is O(n^2). The space-complexity is O(n^2).

Let's check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    int editDistance(string word1, string word2) {
        int m = word1.length();
        int n = word2.length();

        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }

        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]});
                }
            }
        }

        return dp[m][n];
    }
};

Golang solution

func editDistance(word1 string, word2 string) int {
    m , n := len(word1), len(word2)

    dp := make([][]int, m + 1)

    for i := 0; i < m + 1; i++ {
        dp[i] = make([]int, n + 1)
    }

    for i := 0; i <= m; i++ {
        dp[i][0] = i
    }

    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i - 1] == word2[j - 1] {
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                dp[i][j] = 1 + min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1])
            }
        }
    }

    return dp[m][n]
}

func min(a, b int) int {
    if a < b {
        return a
    }

    return b
}

JavaScript solution

var editDistance = function(word1, word2) {
    let m = word1.length;
    let n = word2.length;

    let dp = Array(m + 1).fill().map(() => Array(n + 1));

    for (let i = 0; i <= m; i++) {
        dp[i][0] = i;
    }

    for (let j = 0; j <= n; j++) {
        dp[0][j] = j;
    }

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]);
            }
        }
    }

    return dp[m][n];
};

Let's dry-run our algorithm for a few examples to see how the solution works.

Input: word1 = 'horse'
       word2 = 'ros'

Step 1: m = word1.length()
          = 5
        n = word2.length()
          = 3

Step 2: vector<vector<int>> dp(m + 1, vector<int>(n + 1))
        dp[6][4]

Step 3: loop for i = 0; i <= m; i++
            dp[i][0] = i
        for end

        dp = [
               [0, 0, 0, 0],
               [1, 0, 0, 0],
               [2, 0, 0, 0],
               [3, 0, 0, 0],
               [4, 0, 0, 0],
               [5, 0, 0, 0],
             ]

Step 4: loop for j = 0; i <= n; i++
            dp[0][j] = j
        for end

        dp = [
               [0, 1, 2, 3],
               [1, 0, 0, 0],
               [2, 0, 0, 0],
               [3, 0, 0, 0],
               [4, 0, 0, 0],
               [5, 0, 0, 0],
             ]

Step 5: loop for i = 1; i <= m
          1 <= 5
          true

          loop for j = 1; j <= n
            1 <= 3
            true

            if word1[i - 1] == word2[j - 1]
               word1[1 - 1] == word2[1 - 1]
               word1[0] == word2[0]
               'h' == 'r'
               false

            else
              dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
              dp[1][1] = 1 + min(dp[1][1 - 1], dp[1 - 1][1], dp[1 - 1][1 - 1])
                       = 1 + min(dp[1][0], dp[0][1], dp[0][0])
                       = 1 + min(1, 1, 0)
                       = 1 + 0
                       = 1

            j++
            j = 2

          loop for j <= n
            2 <= 3
            true

            if word1[i - 1] == word2[j - 1]
               word1[1 - 1] == word2[2 - 1]
               word1[0] == word2[1]
               'h' == 'o'
               false

            else
              dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
              dp[1][2] = 1 + min(dp[1][2 - 1], dp[1 - 1][2], dp[1 - 1][2 - 1])
                       = 1 + min(dp[1][1], dp[0][2], dp[0][1])
                       = 1 + min(1, 2, 1)
                       = 1 + 1
                       = 2

            j++
            j = 3

          loop for j <= n
            3 <= 3
            true

            if word1[i - 1] == word2[j - 1]
               word1[1 - 1] == word2[3 - 1]
               word1[0] == word2[2]
               'h' == 's'
               false

            else
              dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
              dp[1][3] = 1 + min(dp[1][3 - 1], dp[1 - 1][3], dp[1 - 1][3 - 1])
                       = 1 + min(dp[1][2], dp[0][3], dp[0][2])
                       = 1 + min(2, 3, 2)
                       = 1 + 2
                       = 3

            j++
            j = 4

          loop for j <= n
            4 <= 3
            false

          dp = [
                 [0, 1, 2, 3],
                 [1, 1, 2, 3],
                 [2, 0, 0, 0],
                 [3, 0, 0, 0],
                 [4, 0, 0, 0],
                 [5, 0, 0, 0],
               ]

          i++
          i = 2

Step 6: loop for i <= m
          2 <= 5
          true

          loop for j = 1; j <= n
            1 <= 3
            true

            if word1[i - 1] == word2[j - 1]
               word1[2 - 1] == word2[1 - 1]
               word1[1] == word2[0]
               'o' == 'r'
               false

            else
              dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
              dp[2][1] = 1 + min(dp[2][1 - 1], dp[2 - 1][1], dp[2 - 1][1 - 1])
                       = 1 + min(dp[2][0], dp[1][1], dp[1][0])
                       = 1 + min(2, 1, 1)
                       = 1 + 1
                       = 2

            j++
            j = 2

          loop for j <= n
            2 <= 3
            true

            if word1[i - 1] == word2[j - 1]
               word1[2 - 1] == word2[2 - 1]
               word1[1] == word2[1]
               'o' == 'o'
               true

               dp[i][j] = dp[i - 1][j - 1]
               dp[2][2] = dp[2 - 1][2 - 1]
                        = dp[1][1]
                        = 1

            j++
            j = 3

          loop for j <= n
            3 <= 3
            true

            if word1[i - 1] == word2[j - 1]
               word1[2 - 1] == word2[3 - 1]
               word1[1] == word2[2]
               'o' == 's'
               false

            else
              dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
              dp[2][3] = 1 + min(dp[2][3 - 1], dp[2 - 1][3], dp[2 - 1][3 - 1])
                       = 1 + min(dp[2][2], dp[1][3], dp[1][2])
                       = 1 + min(1, 3, 2)
                       = 1 + 1
                       = 2

            j++
            j = 4

          loop for j <= n
            4 <= 3
            false

          dp = [
                 [0, 1, 2, 3],
                 [1, 1, 2, 3],
                 [2, 2, 1, 2],
                 [3, 0, 0, 0],
                 [4, 0, 0, 0],
                 [5, 0, 0, 0],
               ]

          i++
          i = 3

Step 7: loop for i <= m
          3 <= 5
          true

          loop for j = 1; j <= n
            1 <= 3
            true

            if word1[i - 1] == word2[j - 1]
               word1[3 - 1] == word2[1 - 1]
               word1[2] == word2[0]
               'r' == 'r'
               true

               dp[i][j] = dp[i - 1][j - 1]
               dp[3][1] = dp[3 - 1][1 - 1]
                        = dp[2][0]
                        = 2

            j++
            j = 2

          loop for j <= n
            2 <= 3
            true

            if word1[i - 1] == word2[j - 1]
               word1[3 - 1] == word2[2 - 1]
               word1[2] == word2[1]
               'r' == 'o'
               false

            else
               dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
               dp[3][2] = 1 + min(dp[3][2 - 1], dp[3 - 1][2], dp[3 - 1][2 - 1])
                        = 1 + min(dp[3][1], dp[2][2], dp[2][1])
                        = 1 + min(0, 1, 2)
                        = 1 + 1
                        = 2

            j++
            j = 3

          loop for j <= n
            3 <= 3
            true

            if word1[i - 1] == word2[j - 1]
               word1[3 - 1] == word2[3 - 1]
               word1[2] == word2[2]
               'r' == 's'
               false

            else
               dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
               dp[3][3] = 1 + min(dp[3][3 - 1], dp[3 - 1][3], dp[3 - 1][3 - 1])
                        = 1 + min(dp[3][2], dp[2][3], dp[2][2])
                        = 1 + min(0, 1, 1)
                        = 1 + 1
                        = 2

            j++
            j = 4

          loop for j <= n
            4 <= 3
            false

          dp = [
                 [0, 1, 2, 3],
                 [1, 1, 2, 3],
                 [2, 2, 1, 2],
                 [3, 2, 2, 2],
                 [4, 0, 0, 0],
                 [5, 0, 0, 0],
               ]

          i++
          i = 4

Step 8: loop for i <= m
          4 <= 5
          true

          loop for j = 1; j <= n
            1 <= 3
            true

            if word1[i - 1] == word2[j - 1]
               word1[4 - 1] == word2[1 - 1]
               word1[3] == word2[0]
               's' == 'r'
               false

            else
               dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
               dp[4][1] = 1 + min(dp[4][1 - 1], dp[4 - 1][1], dp[4 - 1][1 - 1])
                        = 1 + min(dp[4][0], dp[3][1], dp[3][0])
                        = 1 + min(4, 2, 3)
                        = 1 + 2
                        = 3

            j++
            j = 2

          loop for j <= n
            2 <= 3
            true

            if word1[i - 1] == word2[j - 1]
               word1[4 - 1] == word2[2 - 1]
               word1[3] == word2[1]
               's' == 'o'
               false

            else
               dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
               dp[4][2] = 1 + min(dp[4][2 - 1], dp[4 - 1][2], dp[4 - 1][2 - 1])
                        = 1 + min(dp[4][1], dp[3][2], dp[3][1])
                        = 1 + min(3, 2, 2)
                        = 1 + 2
                        = 3

            j++
            j = 3

          loop for j <= n
            3 <= 3
            true

            if word1[i - 1] == word2[j - 1]
               word1[4 - 1] == word2[3 - 1]
               word1[3] == word2[2]
               's' == 's'
               true

               dp[i][j] = dp[i - 1][j - 1]
               dp[4][3] = dp[4 - 1][3 - 1]
                        = dp[3][2]
                        = 2

            j++
            j = 4

          loop for j <= n
            4 <= 3
            false

          dp = [
                 [0, 1, 2, 3],
                 [1, 1, 2, 3],
                 [2, 2, 1, 2],
                 [3, 2, 2, 2],
                 [4, 3, 3, 2],
                 [5, 0, 0, 0],
               ]

          i++
          i = 5

Step 9: loop for i <= m
          5 <= 5
          true

          loop for j = 1; j <= n
            1 <= 3
            true

            if word1[i - 1] == word2[j - 1]
               word1[5 - 1] == word2[1 - 1]
               word1[4] == word2[0]
               'e' == 'r'
               false

            else
               dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
               dp[5][1] = 1 + min(dp[5][1 - 1], dp[5 - 1][1], dp[5 - 1][1 - 1])
                        = 1 + min(dp[5][0], dp[4][1], dp[4][0])
                        = 1 + min(5, 3, 4)
                        = 1 + 3
                        = 4

            j++
            j = 2

          loop for j = 1; j <= n
            2 <= 3
            true

            if word1[i - 1] == word2[j - 1]
               word1[5 - 1] == word2[2 - 1]
               word1[4] == word2[1]
               'e' == 'o'
               false

            else
               dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
               dp[5][2] = 1 + min(dp[5][2 - 1], dp[5 - 1][2], dp[5 - 1][2 - 1])
                        = 1 + min(dp[5][1], dp[4][2], dp[4][1])
                        = 1 + min(4, 3, 3)
                        = 1 + 3
                        = 4

            j++
            j = 3

          loop for j = 1; j <= n
            3 <= 3
            true

            if word1[i - 1] == word2[j - 1]
               word1[5 - 1] == word2[3 - 1]
               word1[4] == word2[2]
               'e' == 's'
               false

            else
               dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
               dp[5][3] = 1 + min(dp[5][3 - 1], dp[5 - 1][3], dp[5 - 1][3 - 1])
                        = 1 + min(dp[5][2], dp[4][3], dp[4][2])
                        = 1 + min(4, 2, 3)
                        = 1 + 2
                        = 3

            j++
            j = 4

          loop for j = 1; j <= n
            4 <= 3
            false

          dp = [
                 [0, 1, 2, 3],
                 [1, 1, 2, 3],
                 [2, 2, 1, 2],
                 [3, 2, 2, 2],
                 [4, 3, 3, 2],
                 [5, 4, 4, 3],
               ]

          i++
          i = 6

Step 10: loop for i <= m
           6 <= 5
           false

Step 11: return dp[m][n]
                dp[5][3]
                3

We return the answer as 3.

LeetCode - Find the Prefix Common Array of Two Arrays

Alkesh Ghorpade — Sun, 30 Apr 2023 16:45:12 +0000

Problem statement

You are given two 0-indexed integer permutations A and B of length n.

A prefix common array of A and B is an array C such that C[i] is equal to the count of numbers that are present at or before the index i in both A and B.

Return the **prefix common array* of A and B*.

A sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.

Problem statement taken from: https://leetcode.com/problems/find-the-prefix-common-array-of-two-arrays

Example 1:

Input: A = [1, 3, 2, 4], B = [3, 1, 2, 4]
Output: [0, 2, 3, 4]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: 1 and 3 are common in A and B, so C[1] = 2.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.
At i = 3: 1, 2, 3, and 4 are common in A and B, so C[3] = 4.

Example 2:

Input: A = [2, 3, 1], B = [3, 1, 2]
Output: [0, 1, 3]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: only 3 is common in A and B, so C[1] = 1.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.

Constraints:

- 1 <= A.length == B.length == n <= 50
- 1 <= A[i], B[i] <= n
- It is guaranteed that A and B are both a permutation of n integers.

Explanation

Brute Force

We need to return an array result of the same length such that result[i] is the number of elements that are common in both A and B. We can start by creating two hash maps map1 and m2 to store the indices of each element in A and B, respectively.

We then iterate over array A and count the number of elements that are common to both A and B up to that point. We do this by checking if the index of each element in A is less than or equal to i and the index of the same element in B is also less than or equal to i. We store the count in an array result and return it as the answer.

A C++ snippet of the above approach is as follows:

vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
    int n = A.size();
    unordered_map<int, int> map1, map2;

    for(int i = 0; i < n; i++) {
        map1[A[i]] = i;
        map2[B[i]] = i;
    }

    vector<int> result(n);

    for(int i = 0; i < n; i++) {
        int count = 0;

        for(int j = 0; j <= i; j++) {
            if(m1[A[j]] <= i && m2[A[j]] <= i) {
                count++;
            }
        }

        result[i] = count;
    }

    return result;
}

The time complexity of this solution is O(n^2), since we are using two nested for loops. The space complexity is O(n).

Efficient solution

To find the prefix common array, we can iterate over arrays A and B simultaneously and keep track of the frequency of each integer in both arrays using an array seen. For each element in A and B, we increment the corresponding element in seen and check if its frequency becomes 2. If the frequency becomes 2, it means that the element is present in both A and B at or before the current index i.

We update the corresponding element in the result array result by adding 1 if the frequency of the element in A or B becomes 2, otherwise we add 0.

Finally, we compute the prefix sum of the result array to get the prefix common array of A and B.

Let's check the algorithm to understand it clearly.

Algorithm

- set current = 0
      n = A.size()

- set result(n)
      seen(n + 1)

- loop for i = 0; i < n; i++
  - seen[A[i]] = seen[A[i]] + 1
  - if seen[A[i]] == 2
    - current++
  - if end

  - seen[B[i]] = seen[B[i]] + 1
  - if seen[B[i]] == 2
    - current++
  - if end

  - result[i] = current
- for end

- return result

The time complexity of this approach is O(n). The space complexity of this approach is O(n).

Let's check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int current = 0, n = A.size();
        vector<int> result(n), seen(n + 1);

        for (int i = 0; i < n; ++i) {
            if (++seen[A[i]] == 2) {
                current++;
            }

            if (++seen[B[i]] == 2) {
                current++;
            }

            result[i] = current;
        }
        return result;
    }
};

Golang solution

func findThePrefixCommonArray(A []int, B []int) []int {
    current, n := 0, len(A)
    result, seen := make([]int, n), make([]int, n + 1)

    for i := 0; i < n; i++ {
        seen[A[i]]++
        if seen[A[i]] == 2 {
            current++
        }

        seen[B[i]]++
        if seen[B[i]] == 2 {
            current++
        }

        result[i] = current
    }

    return result
}

JavaScript solution

var findThePrefixCommonArray = function(A, B) {
    let current = 0, n = A.length;
    let result = new Array(n), seen = new Array(n + 1).fill(0);

    for (let i = 0; i < n; ++i) {
        if (++seen[A[i]] == 2) {
            current++;
        }

        if (++seen[B[i]] == 2) {
            current++;
        }

        result[i] = current;
    }

    return result;
};

Let's dry-run our algorithm for a few examples to see how the solution works.

Input: A = [1, 3, 2, 4]
       B = [3, 1, 2, 4]

Step 1: int current = 0, n = A.size();
        vector<int> result(n), seen(n + 1);

Step 2: loop for i = 0; i < n;
          0 < 4
          true

          if ++seen[A[i]] == 2
            A[i] = A[0]
                 = 1

            seen[A[i]] = seen[A[0]]
                       = seen[1]
                       = 0

            ++seen[A[i]] = 1

            1 == 2
            false

            seen = [0, 1, 0, 0, 0]

          if ++seen[B[i]] == 2
            B[i] = B[0]
                 = 3

            seen[B[i]] = seen[B[0]]
                       = seen[3]
                       = 0

            ++seen[B[i]] = 1

            1 == 2
            false

            seen = [0, 1, 0, 1, 0]

          result[i] = current
          result[0] = 0
          result = [0, 0, 0, 0]

          i++
          i = 1

Step 3: for i < n
          1 < 4
          true

          if ++seen[A[i]] == 2
            A[i] = A[1]
                 = 3

            seen[A[i]] = seen[A[1]]
                       = seen[3]
                       = 1

            ++seen[A[i]] = 2

            2 == 2
            true
            current++
            current = 1

            seen = [0, 1, 0, 2, 0]

          if ++seen[B[i]] == 2
            B[i] = B[1]
                 = 1

            seen[B[i]] = seen[B[0]]
                       = seen[1]
                       = 1

            ++seen[B[i]] = 2

            2 == 2
            true

            current++
            current = 2

            seen = [0, 2, 0, 2, 0]

          result[i] = current
          result[1] = 2
          result = [0, 2, 0, 0]

          i++
          i = 2

Step 4: for i < n
          2 < 4
          true

          if ++seen[A[i]] == 2
            A[i] = A[2]
                 = 2

            seen[A[i]] = seen[A[2]]
                       = seen[2]
                       = 0

            ++seen[A[i]] = 1

            1 == 2
            false

            seen = [0, 2, 1, 2, 0]

          if ++seen[B[i]] == 2
            B[i] = B[2]
                 = 2

            seen[B[i]] = seen[B[2]]
                       = seen[2]
                       = 1

            ++seen[B[i]] = 2

            2 == 2
            true

            current++
            current = 3

            seen = [0, 2, 2, 2, 0]

          result[i] = current
          result[2] = 3
          result = [0, 2, 3, 0]

          i++
          i = 3

Step 5: for i < n
          3 < 4
          true

          if ++seen[A[i]] == 2
            A[i] = A[3]
                 = 4

            seen[A[i]] = seen[A[2]]
                       = seen[4]
                       = 0

            ++seen[A[i]] = 1

            1 == 2
            false

            seen = [0, 2, 2, 2, 1]

          if ++seen[B[i]] == 2
            B[i] = B[3]
                 = 4

            seen[B[i]] = seen[B[3]]
                       = seen[4]
                       = 1

            ++seen[B[i]] = 2

            2 == 2
            true

            current++
            current = 4

            seen = [0, 2, 2, 2, 2]

          result[i] = current
          result[3] = 4
          result = [0, 2, 3, 4]

          i++
          i = 4

Step 6: for i < n
          4 < 4
          false

Step 7: return result

We return the result as [0, 2, 3, 4].