SkylineWebZ

A new interval we add could intersect some adjacent intervals in the array. Given the already sorted interval array, one can find overlapping intervals in a contiguous subarray. We identify overlapping interval’s subarray and combine them with new interval to generate a single merged interval. We first add the lower intervals, then this merged interval, and lastly the remaining intervals in the output to preserve the order ordered. C++ Java Python C# JavaScript Output 1 3 4 7 8 10

Given a set of non-overlapping intervals and a new interval, the challenge is to insert the interval at the proper place such that the intervals stay sorted upon insertion. Merge the overlapping intervals should the insertion produce overlapping intervals. Assume that start time drives the sorting of the non-overlapping interval set. Examples are: Table of Content [Simple Approach] Naive Approach Insertion and merging – O(n*log n) Time and O(1) Space The method is to add the new interval to the existing array of intervals and thereafter manage interval overlapping. We shall so combine the overlapping intervals following insertion using the same method as combine Overlapping Intervals. C++ Java Python C# Output 1 3 4 7 8 10

Problem Statement: Letter Combinations of a Phone Number Given a string containing digits from 2 to 9 inclusive, return all possible letter combinations that the number could represent. A mapping of digits to letters (just like on the telephone buttons) is given below. The output should return all possible combinations of letters that can be formed by the digits in the input string. Example: Input: digits = “23” Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”] Input: digits = “” Output: [] Input: digits = “2” Output: [“a”, “b”, “c”] Approach: The problem can be approached by using backtracking or iterative combination generation. We can build the combinations step by step by taking one letter from each digit’s corresponding character set. Steps: Time Complexity: Code Implementation C Code: #include <stdio.h>#include <string.h>#include <stdlib.h>const char* digitToChar[] = { “”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz”};void backtrack(char* digits, int index, char* current, char** result, int* returnSize) { if (index == strlen(digits)) { result[*returnSize] = (char*)malloc(strlen(current) + 1); strcpy(result[*returnSize], current); (*returnSize)++; return; } int digit = digits[index] – ‘0’; for (int i = 0; i < strlen(digitToChar[digit]); i++) { current[index] = digitToChar[digit][i]; backtrack(digits, index + 1, current, result, returnSize); }}char** letterCombinations(char* digits, int* returnSize) { if (digits == NULL || strlen(digits) == 0) { *returnSize = 0; return NULL; } char** result = (char**)malloc(1000 * sizeof(char*)); // Assumption of max size char* current = (char*)malloc(strlen(digits) + 1); *returnSize = 0; backtrack(digits, 0, current, result, returnSize); free(current); return result;}int main() { char digits[] = “23”; int returnSize; char** result = letterCombinations(digits, &returnSize); for (int i = 0; i < returnSize; i++) { printf(“%s\n”, result[i]); free(result[i]); } free(result); return 0;} C++ Code: #include <iostream>#include <vector>#include <string>using namespace std;class Solution {public: vector<string> letterCombinations(string digits) { vector<string> result; if (digits.empty()) return result; vector<string> digitToChar = { “”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz” }; string current; backtrack(digits, 0, current, result, digitToChar); return result; }private: void backtrack(const string& digits, int index, string& current, vector<string>& result, const vector<string>& digitToChar) { if (index == digits.size()) { result.push_back(current); return; } int digit = digits[index] – ‘0’; for (char c : digitToChar[digit]) { current.push_back(c); backtrack(digits, index + 1, current, result, digitToChar); current.pop_back(); } }};int main() { Solution solution; vector<string> result = solution.letterCombinations(“23”); for (const string& combination : result) { cout << combination << endl; } return 0;} Java Code: import java.util.ArrayList;import java.util.List;public class Solution { private static final String[] DIGIT_TO_CHAR = { “”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz” }; public List<String> letterCombinations(String digits) { List<String> result = new ArrayList<>(); if (digits.isEmpty()) return result; StringBuilder current = new StringBuilder(); backtrack(digits, 0, current, result); return result; } private void backtrack(String digits, int index, StringBuilder current, List<String> result) { if (index == digits.length()) { result.add(current.toString()); return; } int digit = digits.charAt(index) – ‘0’; for (char c : DIGIT_TO_CHAR[digit].toCharArray()) { current.append(c); backtrack(digits, index + 1, current, result); current.deleteCharAt(current.length() – 1); // Backtrack } } public static void main(String[] args) { Solution solution = new Solution(); List<String> result = solution.letterCombinations(“23”); for (String combination : result) { System.out.println(combination); } }} Python Code: from typing import Listclass Solution: def letterCombinations(self, digits: str) -> List[str]: if not digits: return [] digit_to_char = [ “”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz” ] result = [] self._backtrack(digits, 0, “”, result, digit_to_char) return result def _backtrack(self, digits: str, index: int, current: str, result: List[str], digit_to_char: List[str]): if index == len(digits): result.append(current) return digit = int(digits[index]) for char in digit_to_char[digit]: self._backtrack(digits, index + 1, current + char, result, digit_to_char)# Example usagesolution = Solution()print(solution.letterCombinations(“23”)) C# Code: using System;using System.Collections.Generic;public class Solution { private static readonly string[] DigitToChar = { “”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz” }; public IList<string> LetterCombinations(string digits) { var result = new List<string>(); if (string.IsNullOrEmpty(digits)) return result; Backtrack(digits, 0, “”, result); return result; } private void Backtrack(string digits, int index, string current, IList<string> result) { if (index == digits.Length) { result.Add(current); return; } int digit = digits[index] – ‘0’; foreach (char c in DigitToChar[digit]) { Backtrack(digits, index + 1, current + c, result); } } public static void Main() { Solution solution = new Solution(); var result = solution.LetterCombinations(“23”); foreach (var combination in result) { Console.WriteLine(combination); } }} JavaScript Code: var letterCombinations = function(digits) { if (digits === “”) return []; const digitToChar = [ “”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz” ]; let result = []; function backtrack(index, current) { if (index === digits.length) { result.push(current); return; } let digit = digits[index] – ‘0’; for (let char of digitToChar[digit]) { backtrack(index + 1, current + char); } } backtrack(0, “”); return result;};// Example usageconsole.log(letterCombinations(“23”)); Explanation: Time Complexity:

Under the former method, we iteratively search throughout all the remaining ranges until the end for every range we are looking for potential overlaps. Examining just those intervals that coincide with the latest merged interval will help us maximize this. The intervals will be arranged according on starting point, hence if we come across an interval whose starting time falls outside the last merged interval, all subsequent intervals will likewise lie outside it. First, one sorts the intervals according to their initial places intuitively. Comparing each interval with the last merged interval lets us quickly spot overlapping intervals. Iterate over every interval now; if the current interval crosses the last merged interval, combine both of them. Otherwise, add the resultant combined interval. C++ Java Python C# Output 1 6 7 8

Problem Statement: Longest Common Prefix Given a list of strings, find the longest common prefix (LCP) string amongst them. If there is no common prefix, return an empty string. Note: Example: Input: pythonCopy code[“flower”, “flow”, “flight”] Output: pythonCopy code”fl” Input: pythonCopy code[“dog”, “racecar”, “car”] Output: pythonCopy code”” Approach: There are several methods to solve this problem, but the most common ones include: For simplicity and efficiency, we will use the Horizontal Scanning approach here. Approach (Horizontal Scanning): Time Complexity: Code Implementation C Code: #include <stdio.h>#include <string.h>char* longestCommonPrefix(char **strs, int strsSize) { if (strsSize == 0) return “”; // Initialize the prefix as the first string char *prefix = strs[0]; // Compare with each string for (int i = 1; i < strsSize; i++) { // Keep reducing the prefix while it doesn’t match the start of strs[i] while (strncmp(prefix, strs[i], strlen(prefix)) != 0) { // Reduce the prefix by one character from the end prefix[strlen(prefix) – 1] = ‘\0’; } } return prefix;}int main() { char* strs[] = {“flower”, “flow”, “flight”}; int strsSize = 3; printf(“Longest Common Prefix: %s\n”, longestCommonPrefix(strs, strsSize)); // Output: “fl” return 0;} C++ Code: #include <iostream>#include <vector>#include <string>using namespace std;string longestCommonPrefix(vector<string>& strs) { if (strs.empty()) return “”; string prefix = strs[0]; for (int i = 1; i < strs.size(); i++) { while (strs[i].find(prefix) != 0) { prefix = prefix.substr(0, prefix.size() – 1); } } return prefix;}int main() { vector<string> strs = {“flower”, “flow”, “flight”}; cout << “Longest Common Prefix: ” << longestCommonPrefix(strs) << endl; // Output: “fl” return 0;} Java Code: public class Solution { public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) return “”; String prefix = strs[0]; for (int i = 1; i < strs.length; i++) { while (strs[i].indexOf(prefix) != 0) { prefix = prefix.substring(0, prefix.length() – 1); } } return prefix; } public static void main(String[] args) { Solution solution = new Solution(); String[] strs = {“flower”, “flow”, “flight”}; System.out.println(“Longest Common Prefix: ” + solution.longestCommonPrefix(strs)); // Output: “fl” }} Python Code: def longestCommonPrefix(strs): if not strs: return “” prefix = strs[0] for string in strs[1:]: while not string.startswith(prefix): prefix = prefix[:-1] if not prefix: return “” return prefix# Example Usagestrs = [“flower”, “flow”, “flight”]print(“Longest Common Prefix:”, longestCommonPrefix(strs)) # Output: “fl” C# Code: using System;public class Solution { public string LongestCommonPrefix(string[] strs) { if (strs.Length == 0) return “”; string prefix = strs[0]; foreach (var str in strs) { while (!str.StartsWith(prefix)) { prefix = prefix.Substring(0, prefix.Length – 1); if (prefix == “”) return “”; } } return prefix; } public static void Main() { Solution solution = new Solution(); string[] strs = {“flower”, “flow”, “flight”}; Console.WriteLine(“Longest Common Prefix: ” + solution.LongestCommonPrefix(strs)); // Output: “fl” }} JavaScript Code: var longestCommonPrefix = function(strs) { if (strs.length === 0) return ”; let prefix = strs[0]; for (let i = 1; i < strs.length; i++) { while (!strs[i].startsWith(prefix)) { prefix = prefix.substring(0, prefix.length – 1); if (prefix === ”) return ”; } } return prefix;};console.log(longestCommonPrefix([“flower”, “flow”, “flight”])); // Output: “fl” Explanation: Edge Cases: Summary:

The challenge is to combine all the overlapping intervals into one and produce the output which should include only mutually exclusive intervals given an array of time intervals whereby arr[i] = [starti, endi]. As an illustration,: Table of Content [Naive Approach] Checking All Possible Overlaps – O(n^2) Time and O(1) Space One might start from the first interval and compare it with every other interval for overlaps by first grouping all the intervals and then. Eliminate the other interval from the list and combine the other into the first interval if the first interval crosses any other interval. Proceed similarly for the next intervals following the first. C++ Java Python C# JavaScript Output 1 6 7 8

Problem Statement: Roman to Integer The task is to convert a given Roman numeral to its corresponding integer value. Roman numerals are written by combining symbols, and a smaller numeral placed before a larger numeral means subtraction. For example: You are to implement a function that converts a given Roman numeral string into an integer. Roman Numeral Symbols: Example: Input: Output: Input: Output: Input: Output: Input: Output: Input: Output: Approach: Time Complexity: Code Implementation C Code: include <stdio.h>#include <string.h>int romanToInt(char *s) { // Roman numeral to integer mappings int roman[] = {1000, 500, 100, 50, 10, 5, 1}; char *romans[] = {“M”, “D”, “C”, “L”, “X”, “V”, “I”}; int result = 0; int len = strlen(s); for (int i = 0; i < len; i++) { int value = 0; // Find the value of current character for (int j = 0; j < 7; j++) { if (s[i] == romans[j][0]) { value = roman[j]; break; } } // If next character represents a larger value, subtract the current value if (i < len – 1) { int nextValue = 0; for (int j = 0; j < 7; j++) { if (s[i + 1] == romans[j][0]) { nextValue = roman[j]; break; } } if (value < nextValue) { result -= value; } else { result += value; } } else { result += value; } } return result;}int main() { char s[] = “MCMXCIV”; printf(“Integer value of %s is: %d\n”, s, romanToInt(s)); // Output: 1994 return 0;} C++ Code: #include <iostream>#include <unordered_map>#include <string>using namespace std;int romanToInt(string s) { unordered_map<char, int> romanMap = { {‘I’, 1}, {‘V’, 5}, {‘X’, 10}, {‘L’, 50}, {‘C’, 100}, {‘D’, 500}, {‘M’, 1000} }; int result = 0; int len = s.length(); for (int i = 0; i < len; i++) { int value = romanMap[s[i]]; // If the next character represents a larger value, subtract the current value if (i < len – 1 && value < romanMap[s[i + 1]]) { result -= value; } else { result += value; } } return result;}int main() { string s = “MCMXCIV”; cout << “Integer value of ” << s << ” is: ” << romanToInt(s) << endl; // Output: 1994 return 0;} Java Code: import java.util.HashMap;public class Solution { public int romanToInt(String s) { // Roman numeral to integer mapping HashMap<Character, Integer> romanMap = new HashMap<>(); romanMap.put(‘I’, 1); romanMap.put(‘V’, 5); romanMap.put(‘X’, 10); romanMap.put(‘L’, 50); romanMap.put(‘C’, 100); romanMap.put(‘D’, 500); romanMap.put(‘M’, 1000); int result = 0; int len = s.length(); for (int i = 0; i < len; i++) { int value = romanMap.get(s.charAt(i)); // If next character represents a larger value, subtract the current value if (i < len – 1 && value < romanMap.get(s.charAt(i + 1))) { result -= value; } else { result += value; } } return result; } public static void main(String[] args) { Solution solution = new Solution(); String s = “MCMXCIV”; System.out.println(“Integer value of ” + s + ” is: ” + solution.romanToInt(s)); // Output: 1994 }} Python Code: def romanToInt(s: str) -> int: roman_map = {‘I’: 1, ‘V’: 5, ‘X’: 10, ‘L’: 50, ‘C’: 100, ‘D’: 500, ‘M’: 1000} result = 0 length = len(s) for i in range(length): value = roman_map[s[i]] # If next character represents a larger value, subtract the current value if i < length – 1 and value < roman_map[s[i + 1]]: result -= value else: result += value return result# Example Usages = “MCMXCIV”print(f”Integer value of {s} is: {romanToInt(s)}”) # Output: 1994 C# Code: using System;using System.Collections.Generic;public class Solution { public int RomanToInt(string s) { // Roman numeral to integer mapping var romanMap = new Dictionary<char, int> { {‘I’, 1}, {‘V’, 5}, {‘X’, 10}, {‘L’, 50}, {‘C’, 100}, {‘D’, 500}, {‘M’, 1000} }; int result = 0; int len = s.Length; for (int i = 0; i < len; i++) { int value = romanMap[s[i]]; // If next character represents a larger value, subtract the current value if (i < len – 1 && value < romanMap[s[i + 1]]) { result -= value; } else { result += value; } } return result; } public static void Main() { Solution solution = new Solution(); string s = “MCMXCIV”; Console.WriteLine($”Integer value of {s} is: {solution.RomanToInt(s)}”); // Output: 1994 }} JavaScript Code: var romanToInt = function(s) { const romanMap = { ‘I’: 1, ‘V’: 5, ‘X’: 10, ‘L’: 50, ‘C’: 100, ‘D’: 500, ‘M’: 1000 }; let result = 0; let length = s.length; for (let i = 0; i < length; i++) { let value = romanMap[s[i]]; // If next character represents a larger value, subtract the current value if (i < length – 1 && value < romanMap[s[i + 1]]) { result -= value; } else { result += value; } } return result;};console.log(romanToInt(“MCMXCIV”)); // Output: 1994 Summary:

Problem Statement: Integer to Roman The task is to convert a given integer to its equivalent Roman numeral. Roman numerals are represented by seven symbols: Roman numerals are usually written in descending order from left to right, but there are exceptions for certain combinations that represent numbers in a more compact form. For example: Example: Input: Output: Input: Output: Approach: Time Complexity: Code Implementation C Code: #include <stdio.h>#include <string.h>void intToRoman(int num, char* result) { // List of Roman numerals and their corresponding values const int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}; const char* numerals[] = {“M”, “CM”, “D”, “CD”, “C”, “XC”, “L”, “XL”, “X”, “IX”, “V”, “IV”, “I”}; int i = 0; result[0] = ‘\0’; // Initialize result as an empty string while (num > 0) { while (num >= values[i]) { strcat(result, numerals[i]); num -= values[i]; } i++; }}int main() { int num = 1994; char result[20]; intToRoman(num, result); printf(“Roman numeral of %d is: %s\n”, num, result); return 0;} C++ Code: #include <iostream>#include <vector>#include <string>using namespace std;string intToRoman(int num) { vector<pair<int, string>> values = { {1000, “M”}, {900, “CM”}, {500, “D”}, {400, “CD”}, {100, “C”}, {90, “XC”}, {50, “L”}, {40, “XL”}, {10, “X”}, {9, “IX”}, {5, “V”}, {4, “IV”}, {1, “I”} }; string result = “”; for (auto& [value, numeral] : values) { while (num >= value) { result += numeral; num -= value; } } return result;}int main() { int num = 1994; cout << “Roman numeral of ” << num << ” is: ” << intToRoman(num) << endl; return 0;} Java Code: public class Solution { public String intToRoman(int num) { String[] romans = {“M”, “CM”, “D”, “CD”, “C”, “XC”, “L”, “XL”, “X”, “IX”, “V”, “IV”, “I”}; int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}; StringBuilder result = new StringBuilder(); for (int i = 0; i < values.length; i++) { while (num >= values[i]) { result.append(romans[i]); num -= values[i]; } } return result.toString(); } public static void main(String[] args) { Solution solution = new Solution(); int num = 1994; System.out.println(“Roman numeral of ” + num + ” is: ” + solution.intToRoman(num)); }} Python Code: def intToRoman(num: int) -> str: values = [ (1000, “M”), (900, “CM”), (500, “D”), (400, “CD”), (100, “C”), (90, “XC”), (50, “L”), (40, “XL”), (10, “X”), (9, “IX”), (5, “V”), (4, “IV”), (1, “I”) ] result = [] for value, numeral in values: while num >= value: result.append(numeral) num -= value return ”.join(result)# Example Usagenum = 1994print(f”Roman numeral of {num} is: {intToRoman(num)}”) C# Code: using System;using System.Text;public class Solution { public string IntToRoman(int num) { var values = new int[] {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}; var numerals = new string[] {“M”, “CM”, “D”, “CD”, “C”, “XC”, “L”, “XL”, “X”, “IX”, “V”, “IV”, “I”}; StringBuilder result = new StringBuilder(); for (int i = 0; i < values.Length; i++) { while (num >= values[i]) { result.Append(numerals[i]); num -= values[i]; } } return result.ToString(); } public static void Main() { Solution solution = new Solution(); int num = 1994; Console.WriteLine($”Roman numeral of {num} is: {solution.IntToRoman(num)}”); }} JavaScript Code: var intToRoman = function(num) { const values = [ [1000, “M”], [900, “CM”], [500, “D”], [400, “CD”], [100, “C”], [90, “XC”], [50, “L”], [40, “XL”], [10, “X”], [9, “IX”], [5, “V”], [4, “IV”], [1, “I”] ]; let result = ”; for (let [value, numeral] of values) { while (num >= value) { result += numeral; num -= value; } } return result;};console.log(intToRoman(1994)); // Output: “MCMXCIV” Summary: