SkylineWebZ

Problem Statement: 3Sum Closest Description: Given an integer array nums of length n, and an integer target, you need to find three integers in the array such that their sum is closest to the target. Return the sum of the three integers. Note: Constraints: Approach: Example: For input: nums = [-1, 2, 1, -4], target = 1 Output: 2 Explanation: The sum that is closest to 1 is (-1 + 2 + 1 = 2). Code Implementation in Different Languages: C: #include <stdio.h>#include <stdlib.h>#include <math.h>int compare(const void *a, const void *b) { return (*(int*)a – *(int*)b);}int threeSumClosest(int* nums, int numsSize, int target) { qsort(nums, numsSize, sizeof(int), compare); int closest = nums[0] + nums[1] + nums[2]; for (int i = 0; i < numsSize – 2; i++) { int left = i + 1, right = numsSize – 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (abs(sum – target) < abs(closest – target)) { closest = sum; } if (sum < target) { left++; } else if (sum > target) { right–; } else { return sum; } } } return closest;}int main() { int nums[] = {-1, 2, 1, -4}; int size = sizeof(nums) / sizeof(nums[0]); int target = 1; printf(“Closest sum: %d\n”, threeSumClosest(nums, size, target)); return 0;} C++: #include <iostream>#include <vector>#include <algorithm>#include <cmath>using namespace std;int threeSumClosest(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); int closest = nums[0] + nums[1] + nums[2]; for (int i = 0; i < nums.size() – 2; i++) { int left = i + 1, right = nums.size() – 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (abs(sum – target) < abs(closest – target)) { closest = sum; } if (sum < target) { left++; } else if (sum > target) { right–; } else { return sum; } } } return closest;}int main() { vector<int> nums = {-1, 2, 1, -4}; int target = 1; cout << “Closest sum: ” << threeSumClosest(nums, target) << endl; return 0;} Java: import java.util.*;public class Main { public static int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int closest = nums[0] + nums[1] + nums[2]; for (int i = 0; i < nums.length – 2; i++) { int left = i + 1, right = nums.length – 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (Math.abs(sum – target) < Math.abs(closest – target)) { closest = sum; } if (sum < target) { left++; } else if (sum > target) { right–; } else { return sum; } } } return closest; } public static void main(String[] args) { int[] nums = {-1, 2, 1, -4}; int target = 1; System.out.println(“Closest sum: ” + threeSumClosest(nums, target)); }} Python: def threeSumClosest(nums, target): nums.sort() closest = nums[0] + nums[1] + nums[2] for i in range(len(nums) – 2): left, right = i + 1, len(nums) – 1 while left < right: total = nums[i] + nums[left] + nums[right] if abs(total – target) < abs(closest – target): closest = total if total < target: left += 1 elif total > target: right -= 1 else: return total return closest# Example usagenums = [-1, 2, 1, -4]target = 1print(threeSumClosest(nums, target)) JavaScript: function threeSumClosest(nums, target) { nums.sort((a, b) => a – b); let closest = nums[0] + nums[1] + nums[2]; for (let i = 0; i < nums.length – 2; i++) { let left = i + 1, right = nums.length – 1; while (left < right) { let sum = nums[i] + nums[left] + nums[right]; if (Math.abs(sum – target) < Math.abs(closest – target)) { closest = sum; } if (sum < target) { left++; } else if (sum > target) { right–; } else { return sum; } } } return closest;}// Example usagelet nums = [-1, 2, 1, -4];let target = 1;console.log(threeSumClosest(nums, target)); C#: using System;class Program { public static int ThreeSumClosest(int[] nums, int target) { Array.Sort(nums); int closest = nums[0] + nums[1] + nums[2]; for (int i = 0; i < nums.Length – 2; i++) { int left = i + 1, right = nums.Length – 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (Math.Abs(sum – target) < Math.Abs(closest – target)) { closest = sum; } if (sum < target) { left++; } else if (sum > target) { right–; } else { return sum; } } } return closest; } static void Main() { int[] nums = {-1, 2, 1, -4}; int target = 1; Console.WriteLine(“Closest sum: ” + ThreeSumClosest(nums, target)); }} Conclusion: The 3Sum Closest problem can be efficiently solved using the two-pointer technique after sorting the array. The solution works in O(n^2) time complexity, making it suitable for large input sizes. By iterating over each element and adjusting the two pointers, we are able to track the closest sum to the target value.

Problem Statement: 3Sum Description: Given an integer array nums, your task is to find all unique triplets in the array that sum up to zero. Constraints: Example 1: Input: nums = [-1, 0, 1, 2, -1, -4]Output: [[-1, -1, 2], [-1, 0, 1]] Example 2: Input: nums = []Output: [] Example 3: Input: nums = [0, 1, 1]Output: [] Approach: Code Implementation in Different Languages: C: #include <stdio.h>#include <stdlib.h>void threeSum(int* nums, int numsSize) { qsort(nums, numsSize, sizeof(int), compare); for (int i = 0; i < numsSize – 2; i++) { if (i > 0 && nums[i] == nums[i-1]) continue; // Skip duplicates int left = i + 1, right = numsSize – 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { printf(“[%d, %d, %d]\n”, nums[i], nums[left], nums[right]); while (left < right && nums[left] == nums[left+1]) left++; // Skip duplicates while (left < right && nums[right] == nums[right-1]) right–; // Skip duplicates left++; right–; } else if (sum < 0) { left++; } else { right–; } } }}int compare(const void* a, const void* b) { return (*(int*)a – *(int*)b);}int main() { int nums[] = {-1, 0, 1, 2, -1, -4}; int size = sizeof(nums) / sizeof(nums[0]); threeSum(nums, size); return 0;} C++: #include <iostream>#include <vector>#include <algorithm>using namespace std;vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size() – 2; i++) { if (i > 0 && nums[i] == nums[i – 1]) continue; // Skip duplicates int left = i + 1, right = nums.size() – 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { result.push_back({nums[i], nums[left], nums[right]}); while (left < right && nums[left] == nums[left + 1]) left++; // Skip duplicates while (left < right && nums[right] == nums[right – 1]) right–; // Skip duplicates left++; right–; } else if (sum < 0) { left++; } else { right–; } } } return result;}int main() { vector<int> nums = {-1, 0, 1, 2, -1, -4}; vector<vector<int>> result = threeSum(nums); for (auto& triplet : result) { for (int num : triplet) { cout << num << ” “; } cout << endl; } return 0;} Java: import java.util.*;public class Main { public static List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length – 2; i++) { if (i > 0 && nums[i] == nums[i – 1]) continue; // Skip duplicates int left = i + 1, right = nums.length – 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { result.add(Arrays.asList(nums[i], nums[left], nums[right])); while (left < right && nums[left] == nums[left + 1]) left++; // Skip duplicates while (left < right && nums[right] == nums[right – 1]) right–; // Skip duplicates left++; right–; } else if (sum < 0) { left++; } else { right–; } } } return result; } public static void main(String[] args) { int[] nums = {-1, 0, 1, 2, -1, -4}; List<List<Integer>> result = threeSum(nums); for (List<Integer> triplet : result) { System.out.println(triplet); } }} Python: def threeSum(nums): nums.sort() result = [] for i in range(len(nums) – 2): if i > 0 and nums[i] == nums[i – 1]: # Skip duplicates continue left, right = i + 1, len(nums) – 1 while left < right: total = nums[i] + nums[left] + nums[right] if total == 0: result.append([nums[i], nums[left], nums[right]]) while left < right and nums[left] == nums[left + 1]: left += 1 # Skip duplicates while left < right and nums[right] == nums[right – 1]: right -= 1 # Skip duplicates left += 1 right -= 1 elif total < 0: left += 1 else: right -= 1 return result# Example usagenums = [-1, 0, 1, 2, -1, -4]print(threeSum(nums)) JavaScript: function threeSum(nums) { nums.sort((a, b) => a – b); let result = []; for (let i = 0; i < nums.length – 2; i++) { if (i > 0 && nums[i] === nums[i – 1]) continue; // Skip duplicates let left = i + 1, right = nums.length – 1; while (left < right) { let sum = nums[i] + nums[left] + nums[right]; if (sum === 0) { result.push([nums[i], nums[left], nums[right]]); while (left < right && nums[left] === nums[left + 1]) left++; // Skip duplicates while (left < right && nums[right] === nums[right – 1]) right–; // Skip duplicates left++; right–; } else if (sum < 0) { left++; } else { right–; } } } return result;}// Example usagelet nums = [-1, 0, 1, 2, -1, -4];console.log(threeSum(nums)); C#: using System;using System.Collections.Generic;class Program { public static IList<IList<int>> ThreeSum(int[] nums) { Array.Sort(nums); List<IList<int>> result = new List<IList<int>>(); for (int i = 0; i < nums.Length – 2; i++) { if (i > 0 && nums[i] == nums[i – 1]) continue; // Skip duplicates int left = i + 1, right = nums.Length – 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { result.Add(new List<int> { nums[i], nums[left], nums[right] }); while (left < right && nums[left] == nums[left + 1]) left++; // Skip duplicates while (left < right && nums[right] == nums[right – 1]) right–; // Skip duplicates left++; right–; } else if (sum < 0) { left++; } else { right–; } } } return result; } static void Main() { int[] nums = {-1, 0, 1, 2, -1, -4}; var result = ThreeSum(nums); foreach (var triplet in result) { Console.WriteLine($”[{string.Join(“, “, triplet)}]”); } }} Conclusion: The 3Sum problem is efficiently solved by sorting the array first and then using the two-pointer technique. This approach ensures that the solution works in O(n^2) time, which is optimal for this type of problem. The key challenge is handling duplicates and ensuring that each triplet is unique.

Problem Statement: “Container With Most Water” Description: Given an integer array height where each element height[i] represents the height of a vertical line drawn at the position i. You are tasked with finding the two lines that together form a container that holds the most water. The container’s capacity is determined by the shorter of the two lines, and the distance between the two lines. Your objective is to determine the maximum amount of water a container can hold. Constraints: Approach: Example: For input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The container that holds the most water is formed between the lines at index 1 and index 8, with a height of 7 and width of 7, so the area is 7 * 7 = 49. Code Implementation in Different Languages: C: #include <stdio.h>int maxArea(int* height, int heightSize) { int left = 0, right = heightSize – 1; int max_area = 0; while (left < right) { int min_height = height[left] < height[right] ? height[left] : height[right]; int width = right – left; int area = min_height * width; if (area > max_area) { max_area = area; } if (height[left] < height[right]) { left++; } else { right–; } } return max_area;}int main() { int height[] = {1, 8, 6, 2, 5, 4, 8, 3, 7}; int size = sizeof(height) / sizeof(height[0]); printf(“Max area: %d\n”, maxArea(height, size)); return 0;} C++: #include <iostream>#include <vector>#include <algorithm>using namespace std;int maxArea(vector<int>& height) { int left = 0, right = height.size() – 1; int max_area = 0; while (left < right) { int min_height = min(height[left], height[right]); int width = right – left; int area = min_height * width; max_area = max(max_area, area); if (height[left] < height[right]) { left++; } else { right–; } } return max_area;}int main() { vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7}; cout << “Max area: ” << maxArea(height) << endl; return 0;} Java: public class Main { public static int maxArea(int[] height) { int left = 0, right = height.length – 1; int maxArea = 0; while (left < right) { int minHeight = Math.min(height[left], height[right]); int width = right – left; int area = minHeight * width; maxArea = Math.max(maxArea, area); if (height[left] < height[right]) { left++; } else { right–; } } return maxArea; } public static void main(String[] args) { int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7}; System.out.println(“Max area: ” + maxArea(height)); }} Python: def maxArea(height): left, right = 0, len(height) – 1 max_area = 0 while left < right: min_height = min(height[left], height[right]) width = right – left area = min_height * width max_area = max(max_area, area) if height[left] < height[right]: left += 1 else: right -= 1 return max_area# Example Usageheight = [1, 8, 6, 2, 5, 4, 8, 3, 7]print(f”Max area: {maxArea(height)}”) JavaScript: function maxArea(height) { let left = 0; let right = height.length – 1; let maxArea = 0; while (left < right) { let minHeight = Math.min(height[left], height[right]); let width = right – left; let area = minHeight * width; maxArea = Math.max(maxArea, area); if (height[left] < height[right]) { left++; } else { right–; } } return maxArea;}// Example Usagelet height = [1, 8, 6, 2, 5, 4, 8, 3, 7];console.log(“Max area:”, maxArea(height)); C#: using System;class Program { public static int MaxArea(int[] height) { int left = 0, right = height.Length – 1; int maxArea = 0; while (left < right) { int minHeight = Math.Min(height[left], height[right]); int width = right – left; int area = minHeight * width; maxArea = Math.Max(maxArea, area); if (height[left] < height[right]) { left++; } else { right–; } } return maxArea; } static void Main() { int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7}; Console.WriteLine(“Max area: ” + MaxArea(height)); }} Conclusion: This problem utilizes the two-pointer technique to efficiently find the solution in O(n) time. By progressively narrowing the search space while tracking the maximum area encountered, we achieve optimal performance even for large inputs.

Problem Statement Given two sorted arrays nums1 and nums2 of sizes m and n, find the median of the combined sorted array. The solution must run in O(log(min(m, n))) time complexity. Examples Example 1: Input: nums1 = [1, 3], nums2 = [2]Output: 2.0Explanation: Combined sorted array = [1, 2, 3], and median is 2. Example 2: Input: nums1 = [1, 2], nums2 = [3, 4]Output: 2.5Explanation: Combined sorted array = [1, 2, 3, 4], and median is (2 + 3) / 2 = 2.5. Approach To solve this problem efficiently, we leverage binary search. The key idea is to partition both arrays such that all elements on the left of the partition are less than or equal to all elements on the right. Steps: Edge Cases: C cCopy code#include <stdio.h> #include <limits.h> #include <stdlib.h> double findMedianSortedArrays(int* nums1, int m, int* nums2, int n) { if (m > n) return findMedianSortedArrays(nums2, n, nums1, m); int low = 0, high = m, halfLen = (m + n + 1) / 2; while (low <= high) { int i = (low + high) / 2; int j = halfLen – i; int maxLeftX = (i == 0) ? INT_MIN : nums1[i – 1]; int minRightX = (i == m) ? INT_MAX : nums1[i]; int maxLeftY = (j == 0) ? INT_MIN : nums2[j – 1]; int minRightY = (j == n) ? INT_MAX : nums2[j]; if (maxLeftX <= minRightY && maxLeftY <= minRightX) { if ((m + n) % 2 == 0) return (fmax(maxLeftX, maxLeftY) + fmin(minRightX, minRightY)) / 2.0; else return fmax(maxLeftX, maxLeftY); } else if (maxLeftX > minRightY) { high = i – 1; } else { low = i + 1; } } return -1.0; // Invalid input } int main() { int m, n; printf(“Enter size of first array: “); scanf(“%d”, &m); int* nums1 = (int*)malloc(m * sizeof(int)); printf(“Enter elements of first array: “); for (int i = 0; i < m; i++) { scanf(“%d”, &nums1[i]); } printf(“Enter size of second array: “); scanf(“%d”, &n); int* nums2 = (int*)malloc(n * sizeof(int)); printf(“Enter elements of second array: “); for (int i = 0; i < n; i++) { scanf(“%d”, &nums2[i]); } double result = findMedianSortedArrays(nums1, m, nums2, n); printf(“Median: %.2f\n”, result); free(nums1); free(nums2); return 0; } C++ cppCopy code#include <bits/stdc++.h> using namespace std; double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1); int m = nums1.size(), n = nums2.size(); int low = 0, high = m, halfLen = (m + n + 1) / 2; while (low <= high) { int i = (low + high) / 2; int j = halfLen – i; int maxLeftX = (i == 0) ? INT_MIN : nums1[i – 1]; int minRightX = (i == m) ? INT_MAX : nums1[i]; int maxLeftY = (j == 0) ? INT_MIN : nums2[j – 1]; int minRightY = (j == n) ? INT_MAX : nums2[j]; if (maxLeftX <= minRightY && maxLeftY <= minRightX) { if ((m + n) % 2 == 0) return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2.0; else return max(maxLeftX, maxLeftY); } else if (maxLeftX > minRightY) { high = i – 1; } else { low = i + 1; } } return -1.0; // Invalid input } int main() { int m, n; cout << “Enter size of first array: “; cin >> m; vector<int> nums1(m); cout << “Enter elements of first array: “; for (int i = 0; i < m; i++) { cin >> nums1[i]; } cout << “Enter size of second array: “; cin >> n; vector<int> nums2(n); cout << “Enter elements of second array: “; for (int i = 0; i < n; i++) { cin >> nums2[i]; } double result = findMedianSortedArrays(nums1, nums2); cout << “Median: ” << result << endl; return 0; } Java javaCopy codeimport java.util.Scanner; public class MedianOfTwoSortedArrays { public static double findMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1); int m = nums1.length, n = nums2.length; int low = 0, high = m, halfLen = (m + n + 1) / 2; while (low <= high) { int i = (low + high) / 2; int j = halfLen – i; int maxLeftX = (i == 0) ? Integer.MIN_VALUE : nums1[i – 1]; int minRightX = (i == m) ? Integer.MAX_VALUE : nums1[i]; int maxLeftY = (j == 0) ? Integer.MIN_VALUE : nums2[j – 1]; int minRightY = (j == n) ? Integer.MAX_VALUE : nums2[j]; if (maxLeftX <= minRightY && maxLeftY <= minRightX) { if ((m + n) % 2 == 0) return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0; else return Math.max(maxLeftX, maxLeftY); } else if (maxLeftX > minRightY) { high = i – 1; } else { low = i + 1; } } return -1.0; // Invalid input } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print(“Enter size of first array: “); int m = sc.nextInt(); int[] nums1 = new int[m]; System.out.println(“Enter elements of first array: “); for (int i = 0; i < m; i++) { nums1[i] = sc.nextInt(); } System.out.print(“Enter size of second array: “); int n = sc.nextInt(); int[] nums2 = new int[n]; System.out.println(“Enter elements of second array: “); for (int i = 0; i < n; i++) { nums2[i] = sc.nextInt(); } double result = findMedianSortedArrays(nums1, nums2); System.out.printf(“Median: %.2f%n”, result); sc.close(); } } Python def findMedianSortedArrays(nums1, nums2): if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 m, n = len(nums1), len(nums2) low, high = 0, m half_len = (m + n + 1) // 2 while low <= high: i = (low + high) // 2 j = half_len – i max_left_x = float(‘-inf’) if i == 0 else nums1[i – 1] min_right_x = float(‘inf’) if i == m else nums1[i] max_left_y = float(‘-inf’) if j == 0 else nums2[j – 1] min_right_y = float(‘inf’) if j == n else nums2[j] if max_left_x <= min_right_y and max_left_y <= min_right_x: if (m + n) % 2 == 0: return (max(max_left_x, max_left_y) + min(min_right_x, min_right_y))

Problem Statement Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the target. Example: Input: nums = [2, 7, 11, 15]target = 9 Output: [0, 1] Explanation: nums[0] + nums[1] = 2 + 7 = 9 Algorithm You can solve this problem in various ways: 1. Brute Force 2. Hash Map (Optimized Solution) Two Sum problem in various programming languages: C CPP JAVA Python pythonCopy codedef two_sum(nums, target): num_map = {} for i, num in enumerate(nums): complement = target – num if complement in num_map: return [num_map[complement], i] num_map[num] = i return [] nums = [2, 7, 11, 15] target = 9 result = two_sum(nums, target) if result: print(result) else: print(“No solution found”) C# using System;using System.Collections.Generic;class TwoSum { public static int[] TwoSumSolution(int[] nums, int target) { Dictionary<int, int> map = new Dictionary<int, int>(); for (int i = 0; i < nums.Length; i++) { int complement = target – nums[i]; if (map.ContainsKey(complement)) { return new int[] { map[complement], i }; } map[nums[i]] = i; } return new int[] {}; } static void Main(string[] args) { int[] nums = {2, 7, 11, 15}; int target = 9; int[] result = TwoSumSolution(nums, target); if (result.Length > 0) { Console.WriteLine($”[{result[0]}, {result[1]}]”); } else { Console.WriteLine(“No solution found”); } }} JavaScript function twoSum(nums, target) { const numMap = new Map(); for (let i = 0; i < nums.length; i++) { const complement = target – nums[i]; if (numMap.has(complement)) { return [numMap.get(complement), i]; } numMap.set(nums[i], i); } return [];}const nums = [2, 7, 11, 15];const target = 9;const result = twoSum(nums, target);if (result.length > 0) { console.log(result);} else { console.log(“No solution found”);}