Posted on

in order traversal

this was the geeks for geeks problem of the day today


/* A Binary Tree node

class Node {
    int data;
    Node left, right;
   Node(int item)    {
        data = item;
        left = right = null;
    }
}
*/
class Solution {
    ArrayList<Integer> result = new ArrayList<>();
    // Function to return a list containing the inorder traversal of the tree.
    ArrayList<Integer> inOrder(Node root) {
        // Code
        
        inOrderHelper(root);
        return result;
    }
    
    private void inOrderHelper( Node root ){
        if( root == null ) return;
        
        inOrderHelper( root.left );
        result.add(root.data);
        inOrderHelper( root.right );

    }
    
}
Posted on

Subarrays with sum K

Given an unsorted array of integers, find the number of continuous subarrays having sum exactly equal to a given number k.

Examples:

Input: arr = [10, 2, -2, -20, 10], k = -10
Output: 3
Explaination: Subarrays: arr[0...3], arr[1...4], arr[3...4] have sum exactly equal to -10.
Input: arr = [9, 4, 20, 3, 10, 5], k = 33
Output: 2
Explaination: Subarrays: arr[0...2], arr[2...4] have sum exactly equal to 33.
Input: arr = [1, 3, 5], k = 0
Output: 0 Explaination: No subarray with 0 sum.

Constraints:

  • 1 ≤ arr.size() ≤ 105
  • -103 ≤ arr[i] ≤ 103
  • -107 ≤ k ≤ 107
class Solution {
  public:
    int countSubarrays(vector<int> &arr, int k) {

    // unordered_map to store prefix sums frequencies
    unordered_map<int, int> prefixSums;
  
    int res = 0;
    int currSum = 0;

    for (int i = 0; i < arr.size(); i++) {
        
        // Add current element to sum so far.
        currSum += arr[i];

        // If currSum is equal to desired sum, then a new
        // subarray is found. So increase count of subarrays.
        if (currSum == k)
            res++;

        // Check if the difference exists in the prefixSums map.
        if (prefixSums.find(currSum - k) != prefixSums.end())
            res += prefixSums[currSum - k];

        // Add currSum to the set of prefix sums.
        prefixSums[currSum]++;
    }

    return res;

    }
};

Posted on

Set Matrix Zeros

class Solution {
  public:
    void setMatrixZeroes(vector<vector<int>> &mat) {
        int n = mat.size();
        int m = mat[0].size();
    
        bool firstRowHasZero = false;
        bool firstColHasZero = false;
    
        // Check if the first row has any zero
        for (int j = 0; j < m; j++) {
            if (mat[0][j] == 0) {
                firstRowHasZero = true;
                break;
            }
        }
    
        // Check if the first column has any zero
        for (int i = 0; i < n; i++) {
            if (mat[i][0] == 0) {
                firstColHasZero = true;
                break;
            }
        }
    
        // Use the first row and column to mark zeros
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (mat[i][j] == 0) {
                    mat[i][0] = 0;
                    mat[0][j] = 0;
                }
            }
        }
    
        // Update the matrix based on the markers
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (mat[i][0] == 0 || mat[0][j] == 0) {
                    mat[i][j] = 0;
                }
            }
        }
    
        // Update the first row if needed
        if (firstRowHasZero) {
            for (int j = 0; j < m; j++) {
                mat[0][j] = 0;
            }
        }
    
        // Update the first column if needed
        if (firstColHasZero) {
            for (int i = 0; i < n; i++) {
                mat[i][0] = 0;
            }
        }
        
    }
};

The idea here is using the first row and column as a Dynamic Programming table to mark which rows and columns need to be zeroed out.
That being done, then first column and row itself is updated at the end.

Posted on

Search Sorted Matrix Solution in C++

The idea here is to implement binary search after discovering the correct row.


#include <bits/stdc++.h>
using namespace std;



class Solution {
  public:
  
  
    // Function to search a given number in row-column sorted matrix.
    bool searchMatrix(vector<vector<int>> &mat, int x) {
        // code here
        vector<int>*row = nullptr;
        int rows = mat.size();
        int cols = mat[0].size();
        
        for( int i = 0; i < rows; i++ ){
            if( mat[i][0] <= x && mat[i][cols-1] >= x ){
                row = &(mat[i]);
                break;
            }
        }
        
        if( row == nullptr ) return false;
        
        auto binarySearch = [row, x]( int low, int high ) -> bool{
            
            while( low <= high ){
                int mid = low + (high-low)/2;
            
                if( (*row)[mid] == x ){
                    return true;
                }else if((*row)[mid] < x ){
                    low =  mid + 1;
                } else {
                    high = mid - 1;
                }
                
            }
            
            return false;
            
        };   
        
        return binarySearch(0, cols -1 );
    }
};

Posted on

Min Chars to Add for Palindrome

Given a string s, the task is to find the minimum characters to be added at the front to make the string palindrome.

Note: A palindrome string is a sequence of characters that reads the same forward and backward.

Examples:

Input: s = "abc"
Output: 2
Explanation: Add 'b' and 'c' at front of above string to make it palindrome : "cbabc"
Input: s = "aacecaaaa"
Output: 2
Explanation: Add 2 a's at front of above string to make it palindrome : "aaaacecaaaa"

Constraints:
1 <= s.size() <= 106

Solution:

To determine the minimum characters to be added at the front of a string to make it a palindrome, we can solve the problem efficiently using a technique involving the longest prefix of the string that is also a suffix (LPS). This can be computed using the KMP algorithm. Below is the explanation, followed by the implementation.

Key Observation:

To make the string a palindrome by adding only characters to the front:

  • We need to find the longest suffix of the string (starting at the end) that is already a palindrome.
  • Once this suffix is identified, the remaining prefix of the string (which isn’t part of that palindromic suffix) will need to be reversed and added to the front of the string. The count of these characters is the output.

This amounts to finding:

  1. The longest prefix-suffix (LPS) of the string concatenated with its reverse (using a special separator character to avoid false matches).

Let’s break this into steps.

Steps to Find the Minimum Characters:

  1. Concatenate the String and Its Reverse:
    • Create a new string: temp = s + "$" + reverse(s) (we use $ or any separator to distinguish the reversed part from the original string).
  2. Compute Longest Prefix Suffix (LPS):
    • Use the KMP (Knuth-Morris-Pratt) algorithm on temp to compute the LPS array.
    • The LPS array gives us the length of the longest prefix of temp that is also a suffix. This indicates the maximum part of s (from the start) that matches the reverse part.
  3. Calculate Minimum Characters to Add:
    • Subtract the longest prefix-suffix from the length of the original string:
Minimum characters to add = s.length() - LPS[length of temp - 1]

Implementation in C++:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// Function to compute the LPS array (used in KMP algorithm)
vector<int> computeLPS(const string& str) {
int n = str.length();
vector<int> lps(n, 0); // LPS array
int len = 0; // Length of previous longest prefix suffix
int i = 1;

// Compute LPS array
while (i < n) {
if (str[i] == str[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1]; // Backtrack
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}

// Function to find minimum characters to add at front to make the string palindrome
int minCharsToMakePalindrome(const string& s) {
string reversedStr = s;
reverse(reversedStr.begin(), reversedStr.end());

// Create the concatenated string
string temp = s + "$" + reversedStr;

// Compute LPS array for the concatenated string
vector<int> lps = computeLPS(temp);

// Length of the longest palindromic suffix
int longestPalindromicPrefix = lps.back();

// Minimum characters to add = length of s - longest palindromic prefix
return s.length() - longestPalindromicPrefix;
}

int main() {
string s;
cout << "Enter string: ";
cin >> s;

int result = minCharsToMakePalindrome(s);

cout << "Minimum characters to add: " << result << endl;

return 0;
}

Explanation of Code:

  1. Reverse the String:
    • Create a reversed copy of s (reversedStr).
  2. Concatenate s, $, and reversedStr:
    • This ensures we identify the longest part of s that matches the reversed portion.
    Example:
    If s = “aacecaaa”, then temp = “aacecaaa$aaacecaa”.
  3. Compute LPS Array:
    • Use the KMP algorithm to compute the longest prefix that is also a suffix for temp.
  4. Find the Num of Characters to Add:
    • Subtract the length of the longest palindromic prefix from the total length of s.
Posted on

 Find Minimum in Rotated Sorted Array

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

  • [4,5,6,7,0,1,2] if it was rotated 4 times.
  • [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 

Key Observations:

  1. A rotated sorted array is a sorted array that has been rotated at some pivot point. For example:
    • Original array: [1, 2, 3, 4, 5]
    • Rotated arrays: [4, 5, 1, 2, 3], [3, 4, 5, 1, 2]
  2. Minimum Element:
    • The minimum element is the only element in the rotated array that is smaller than its predecessor.
    • Alternatively, in the case of no rotation (e.g., [1, 2, 3, 4, 5]), the first element is the smallest.
  3. Binary Search Approach:
    • Since the array is sorted and rotated, we can use binary search to identify the minimum element in O(log n) time.

Steps to Solve:

  1. Binary Search:
    • Set two pointers: low = 0 (start of array) and high = n-1 (end of array).
    • While low < high, compute the middle index: mid = low + (high - low) / 2.
    • Depending on the relationship between arr[mid] and arr[high]:
      • If arr[mid] > arr[high]: The minimum must lie in the right half of the array (set low = mid + 1).
      • Otherwise, the minimum must be in the left half or at mid (set high = mid).
    • When low == high, the minimum element is at index low.
  2. Return the Result:
    • Output the element at arr[low].

Algorithm Complexity:

  • Time Complexity:
    Binary search operates in O(log n) time due to halving the search space in every iteration.
  • Space Complexity:
    The algorithm uses O(1) space as we only manipulate indices and access the array directly.

Implementation in C++:

Here is the efficient implementation:

#include <iostream>
#include <vector>
using namespace std;

int findMinimum(const vector<int>& arr) {
int low = 0, high = arr.size() - 1;

// Binary search to find the minimum element
while (low < high) {
int mid = low + (high - low) / 2;

// If middle element is greater than the last element,
// the minimum must be in the right half
if (arr[mid] > arr[high]) {
low = mid + 1;
}
// Otherwise, the minimum is in the left half (or could be at mid)
else {
high = mid;
}
}

// At this point, low == high and points to the minimum element
return arr[low];
}

int main() {
vector<int> arr = {4, 5, 6, 7, 0, 1, 2}; // Example rotated array
cout << "The minimum element is: " << findMinimum(arr) << endl;

return 0;
}
Posted on

Non Repeating Character

Difficulty: Easy
Accuracy: 40.43%
Submissions: 262K+Points: 2

Given a string s consisting of lowercase Latin Letters. Return the first non-repeating character in s. If there is no non-repeating character, return ‘$’.
Note: When you return ‘$’ driver code will output -1.

Examples:

Input: s = "geeksforgeeks"
Output: 'f'
Explanation: In the given string, 'f' is the first character in the string which does not repeat.
Input: s = "racecar"
Output: 'e'
Explanation: In the given string, 'e' is the only character in the string which does not repeat.
Input: s = "aabbccc"
Output: -1
Explanation: All the characters in the given string are repeating.

Constraints:
1 <= s.size() <= 105

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

char firstNonRepeatingChar(const string& s) {
    // Step 1: Count frequencies of each character
    unordered_map<char, int> charCount;
    for (char c : s) {
        charCount[c]++;
    }

    // Step 2: Find the first non-repeating character
    for (char c : s) {
        if (charCount[c] == 1) {
            return c; // First non-repeating character found
        }
    }

    // Step 3: No non-repeating character
    return '$';
}

int main() {
    string s = "geeksforgeeks";
    char result = firstNonRepeatingChar(s);

    if (result == '$') {
        cout << -1 << endl; // Follow the note: '$' indicates no non-repeating character
    } else {
        cout << result << endl;
    }

    return 0;
}

To solve the problem of finding the first non-repeating character in a string, we can use an efficient approach by incorporating a hashmap (or an equivalent data structure) to count the frequency of characters in the string. Here’s the step-by-step solution:

Steps to Solve:

  1. Count Character Frequencies:
    • Traverse the string and count the occurrences of each character.
    • Store the counts in a dictionary (or a hashmap).
  2. Find the First Non-Repeating Character:
    • Traverse the string again, and for each character, check its frequency in the hashmap.
    • The first character with a frequency of 1 is the first non-repeating character.
  3. Return the Result:
    • If no character has a frequency of 1, return $.

Algorithm Complexity:

  1. Time Complexity:
    • Counting frequencies: O(n) (single traversal for the frequency hashmap).
    • Traversing again to find the first non-repeating character: O(n).
    • Total: O(n).
  2. Space Complexity:
    • Storing frequencies in a hashmap requires O(26) (in the worst case, since there are only 26 lowercase Latin letters). This is O(1) space.
Posted on

Maximum difference between pair in a matrix

https://www.geeksforgeeks.org/problems/maximum-difference-between-pair-in-a-matrix/

Difficulty: Hard
Accuracy: 49.36%
Submissions: 2K+Points: 8

Given an n x n matrix, mat[n][n] of integers. The task is to find the maximum value of mat(c, d)- mat(a, b) over all choices of indexes such that both c > a and d > b.

Example 1:

Input: mat[N][N] = {{ 1, 2, -1, -4, -20 },
             { -8, -3, 4, 2, 1 }, 
             { 3, 8, 6, 1, 3 },
             { -4, -1, 1, 7, -6 },
             { 0, -4, 10, -5, 1 }};
Output: 18
Explanation: The maximum value is 18 as mat[4][2] - mat[1][0] = 18 has maximum difference.

Your Task:  
You don’t need to read input or print anything. Your task is to complete the function findMaxValue() which takes a matrix mat and returns an integer as output.

Expected Time Complexity: O(n2)
Expected Auxiliary Space: O(n2)

Constraints:
1 <= n<= 103
-103<= mat[i][j] <=103

Approach:

  1. Observation: If we fix (c, d) as the bottom-right element of a submatrix, then for any fixed (a, b) where a < c and b < d, the maximum value of mat(c, d) - mat(a, b) depends on the smallest value seen in all submatrices containing (c, d).
  2. Dynamic Programming Strategy:
    • Precompute the max_matrix so that max_matrix[i][j] contains the maximum element in the submatrix starting from (i, j) to the bottom-right corner of the mat.
    • Iterate over all possible (a, b) positions and calculate the maximum difference using max_matrix.
    • Update the result during each iteration.
  3. Algorithm:
    • Start from the bottom right of the matrix and move to the top left.
    • Precompute the max_matrix while iterating.
    • Calculate the result using:
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int findMaxValue(vector<vector<int>>& mat, int n) {
    // Create an auxiliary matrix to store maximum elements
    vector<vector<int>> max_matrix(n, vector<int>(n, 0));

    // Initialize variables
    int max_diff = INT_MIN;

    // Initialize the last value of max_matrix (bottom-right corner)
    max_matrix[n - 1][n - 1] = mat[n - 1][n - 1];

    // Precompute max values for the last row
    for (int j = n - 2; j >= 0; j--) {
        max_matrix[n - 1][j] = max(mat[n - 1][j], max_matrix[n - 1][j + 1]);
    }

    // Precompute max values for the last column
    for (int i = n - 2; i >= 0; i--) {
        max_matrix[i][n - 1] = max(mat[i][n - 1], max_matrix[i + 1][n - 1]);
    }

    // Precompute the rest of the max_matrix and find the maximum difference
    for (int i = n - 2; i >= 0; i--) {
        for (int j = n - 2; j >= 0; j--) {
            // Update the maximum difference
            max_diff = max(max_diff, max_matrix[i + 1][j + 1] - mat[i][j]);

            // Update the max_matrix for position (i, j)
            max_matrix[i][j] = max(mat[i][j], max(max_matrix[i + 1][j], max_matrix[i][j + 1]));
        }
    }

    return max_diff;
}

int main() {
    vector<vector<int>> mat =  {{ 1, 2, -1, -4, -20 },
             { -8, -3, 4, 2, 1 },
             { 3, 8, 6, 1, 3 },
             { -4, -1, 1, 7, -6 },
             { 0, -4, 10, -5, 1 }};
    int n = mat.size();

    cout << "Maximum Difference: " << findMaxValue(mat, n) << endl;

    return 0;
}

Explanation of Code:

  1. Base Cases:
    • The bottom-right cell of max_matrix is initialized as mat[n-1][n-1] because it’s the only element in that submatrix.
    • The last row and column of max_matrix are precomputed since they only depend on the elements to their right and below, respectively.
  2. Updating the Rest of the Matrix:
    • Start from the bottom-right corner and fill up the rest of the matrix.
    • At each cell (i, j), update max_diff using the value:
max_matrix[i+1][j+1] - mat[i][j]
  • Update max_matrix[i][j] to store the maximum element in the submatrix starting at (i, j).
  1. Efficiency:
    • The algorithm runs in O(n^2) since we need to process n^2 values and compute the maximum for each cell in constant time.

Posted on

Find the Peek Element in the Array

Peak element

https://www.geeksforgeeks.org/problems/peak-element
https://leetcode.com/problems/find-peak-element
Difficulty: Basic
Accuracy: 38.86%
Submissions: 510K+Points: 1

Given an array arr[] where no two adjacent elements are same, find the index of a peak element. An element is considered to be a peak if it is greater than its adjacent elements (if they exist). If there are multiple peak elements, return index of any one of them. The output will be “true” if the index returned by your function is correct; otherwise, it will be “false”.

Note: Consider the element before the first element and the element after the last element to be negative infinity.

Examples :

Input: arr = [1, 2, 4, 5, 7, 8, 3]
Output: true
Explanation: arr[5] = 8 is a peak element because arr[4] < arr[5] > arr[6].
Input: arr = [10, 20, 15, 2, 23, 90, 80]
Output: true
Explanation: arr[1] = 20 and arr[5] = 90 are peak elements because arr[0] < arr[1] > arr[2] and arr[4] < arr[5] > arr[6]. 
Input: arr = [1, 2, 3]
Output: true
Explanation: arr[2] is a peak element because arr[1] < arr[2] and arr[2] is the last element, so it has negative infinity to its right.

Constraints:
1 ≤ arr.size() ≤ 106
-231 ≤ arr[i] ≤ 231 – 1

Solution in C++

Algorithm: Uses a binary search approach to find a peak element in O(log n) time complexity.

//
// Created by robert on 12/15/24.
//
#include <iostream>
#include <vector>
using namespace std;

int findPeakElement(const vector<int>& arr) {
    int n = arr.size();
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        // Check if the mid element is a peak
        if ((mid == 0 || arr[mid] > arr[mid - 1]) &&
            (mid == n - 1 || arr[mid] > arr[mid + 1])) {
            return mid; // Peak found
        }

        // If the left neighbor is greater, search on the left side
        if (mid > 0 && arr[mid - 1] > arr[mid]) {
            high = mid - 1;
        }
        // Otherwise, search on the right side
        else {
            low = mid + 1;
        }
    }

    return -1; // This should never be reached
}

int main() {
    vector<int> arr = {1, 2, 4, 5, 7, 8, 3};
    int peakIndex = findPeakElement(arr);
    cout << "Peak element index: " << peakIndex << endl;
    return 0;
}
Posted on

Insert New Interval and Merge Overlapping Intervals

Given an array of non-overlapping intervals intervals where intervals[i] = [start<sub>i</sub>, end<sub>i</sub>] represent the start and the end of the i<sup>th</sup> event and intervals is sorted in ascending order by start<sub>i</sub>. He wants to add a new interval newInterval[newStart, newEnd] where newStart and newEnd represent the start and end of this interval.

Need to insert newInterval into intervals such that intervals is still sorted in ascending order by start<sub>i</sub> and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Examples:

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

Constraints:
1 ≤ intervals.size() ≤  105
0 ≤ start[i], end[i] ≤ 109Try more examples

This problem involves inserting a new interval into a sorted, non-overlapping set of intervals and ensuring the resulting intervals remain sorted and non-overlapping. It also requires merging overlapping intervals as necessary.


Key Steps to Solve the Problem:

  1. Determine Where to Insert the New Interval:
    • Traverse the original list of intervals and insert the new interval in its appropriate position based on its start value.
  2. Merge Overlapping Intervals:
    • After inserting the new interval, traverse the list of intervals and merge any overlapping intervals to ensure the intervals are non-overlapping.
  3. Preserve Sorting:
    • Since the given list is already sorted and we insert the new interval at the correct position, the list remains sorted.

Algorithm:

If there is an overlap (i.e., starti <= newEnd and endi >= newStart), merge the overlapping intervals by updating newInterval to:

Iterate over Intervals:

For each interval in the intervals array, if it does not overlap with newInterval, simply add it to the result.
If there is an overlap (i.e., starti <= newEnd and endi >= newStart), merge the overlapping intervals by updating newInterval to:

newInterval[0] = min(newInterval[0], starti);
newInterval[1] = max(newInterval[1], endi);

Once the merging is complete, the resulting array will be sorted and non-overlapping.

Add Remaining Intervals:

If there are intervals after the position of the merged interval, append them to the result array.

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> insertInterval(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> result; // Resultant array of intervals
    int i = 0, n = intervals.size();

    // Step 1: Add all intervals that come before the new interval
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.push_back(intervals[i]);
        i++;
    }

    // Step 2: Merge overlapping intervals with newInterval
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = min(newInterval[0], intervals[i][0]);
        newInterval[1] = max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.push_back(newInterval); // Add the merged interval

    // Step 3: Add all intervals that come after the new interval
    while (i < n) {
        result.push_back(intervals[i]);
        i++;
    }

    return result;
}

int main() {
    vector<vector<int>> intervals = {{1, 3}, {6, 9}};
    vector<int> newInterval = {2, 5};

    vector<vector<int>> result = insertInterval(intervals, newInterval);
    cout << "Resulting Intervals: ";
    for (const auto& interval : result) {
        cout << "[" << interval[0] << ", " << interval[1] << "] ";
    }
    cout << endl;

    return 0;
}

Complexity Analysis:

  1. Time Complexity:
    • Traversal through all intervals happens once: O(n), where n is the number of intervals.
    • Merging overlapping intervals is constant time per iteration as only the current interval and newInterval are involved.
    Total: O(n).
  2. Space Complexity:
    • Result is stored in a new vector: O(n).
    • Space used for storing merged intervals (in the result).

Edge Cases:

  1. Empty Intervals:
    • intervals = [] and newInterval = [5, 7] → Result: [[5, 7]].
  2. No Overlap:
    • intervals = [[1, 2], [3, 4]] and newInterval = [5, 6] → Result: [[1, 2], [3, 4], [5, 6]].
  3. Complete Overlap:
    • intervals = [[1, 5]] and newInterval = [2, 3] → Result: [[1, 5]].