Author: devangini123

🌙 Problem Statement: You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part. For example, the string “ababcc” can be partitioned into [“abab”, “cc”], but partitions such as [“aba”, “bcc”] or [“ab”, “ab”, “cc”] are invalid. Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s. Return a list of integers representing the size of these parts. Example 1: Input: s = “ababcbacadefegdehijhklij” Output: [9,7,8] Explanation: The partition is “ababcbaca”, “defegde”,…

🌙 Problem Statement: Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input. Example 1: Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]. Example 2: Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping. Example 3: Input: intervals = [[4,7],[1,4]] Output: [[1,7]] Explanation: Intervals [1,4] and [4,7] are considered overlapping. Constraints 1 #include <bits/stdc++.h> using namespace std; vector

🌙 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. Note: that you don’t need to modify intervals in-place. You can…

🌙 Greedy Algorithm Greedy is a problem solving approach where we make locally optimal choices, with a hope that it will lead to global optimal solution. Take best choice at the moment, without worrying about the future. Examples Example 1: Coin Change Problem Given an amount of n rupees and an unlimited supply of coins or notes of denominations {1, 2, 5, 10}. we have to find the minimum number of coins required to make up the 18 amount. Intuition: Firstly, choose the maximum denomination coin. Suppose we choose 10, now 8 is remaining. If we choose the maximum coin…

🌙 Problem Statement: You are given an integer array prices where prices[i] is the price of a given stock on the ith day. On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve. Example 1: Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.…

🌙 Problem Statement: At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a $5 , $10, or $20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5. Note that you do not have any change in hand at first. Given an integer array bills where bills[i] is the bill the ith customer pays, return true if…

🌙 Problem Statement: Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number. Example 1: Input: g =…

🌙 Problem Statement: A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti. Return the minimum cost to fly every person to a city such that exactly n people arrive in each city. Example 1: Input: costs = [[10,20],[30,200],[400,50],[30,20]] Output: 110 Explanation: The first person goes to city A for a cost of 10. The second person goes to city A for a cost of 30. The third…

🌙 Problem Statement: Given a sorted array, this algorithm returns the k elements closest to a target value x. The output is sorted in ascending order. Approach: We apply binary search to find the best starting index of the k closest elements window. We compare arr[m + k] – x and x – arr[m] to decide whether to shift the window left or right. Once we find the optimal window, return the subarray from index l to l + k – 1. Time & Space Complexity: Time Complexity: O(log(n – k) + k) Space Complexity: O(k) Dry Run Input (assumed):…

🌙 Problem Statement: This algorithm finds the single non-duplicate element in a sorted array where every other element appears exactly twice. Approach: Use binary search between left (l) and right (r). At each mid (m): If arr[m] === arr[m – 1], count elements on the left. If that count is odd → single lies left → r = m – 2. If count is even → single lies right → l = m + 1. Same logic applies if arr[m] === arr[m + 1]. If neither left nor right match → return arr[m]. Time & Space Complexity: Time Complexity: O(logn)…