Problem Statement: # Given a m x n grid filled with non-negative integers, find a path from the top left corner to the bottom right corner which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time. Return the minimum path sum. Example: # Input: grid = [ [1, 3, 1], [1, 5, 1], [4, 2, 1] ] Output: 7 Explanation: The path that minimizes the sum is 1→3→1→1→1, which sums to 7. ...
Problem Statement: # Given a string s, partition the string into as many parts as possible so that each letter appears in at most one part, and return the number of partitions you can create. Example: # Input: s = "abacddbec" Output: 4 Explanation: One optimal partitioning is ["abac", "dd", "b", "ec"]. Here, each letter appears in at most one part. Thus, the maximum number of partitions is 4. Solution Approach: # The problem can be solved by first scanning the string to determine the last occurrence of each character. ...
Problem Statement: # Given a 2D grid of 0s and 1s, where 1 represents land and 0 represents water, find the perimeter of the island. The grid cells are connected horizontally/vertically (not diagonally). There is exactly one island, and it doesn’t have lakes (water inside that isn’t connected to the water around the island). The grid is surrounded by water, and there is exactly one island (i.e., one or more connected land cells). ...
Question # Given an integer array nums of n elements, partition it into two non-empty subsets, S1 and S2, such that the absolute difference between the sum of elements in S1 and the sum of elements in S2 is minimized. Return the minimum absolute difference. Example # Input: nums = [1, 2, 3, 4] Output: 0 Explanation: Partitioning the array into subsets [1, 4] and [2, 3] gives two subsets with equal sums of 5, so the minimum absolute difference is 0. ...
Problem Statement: # You are given a list of n servers, where each server has a certain load represented by an integer. Your task is to partition this list into two sublists such that: The absolute difference between the sums of the loads of the two sublists is minimized. Each server belongs to exactly one sublist. The order of servers in the sublists does not matter. Return the minimum possible absolute difference. ...
Problem Statement # You are given a 2D integer grid terrain representing the elevation of a landscape. Imagine that rain falls uniformly across the area and is trapped depending on the terrain’s shape. Calculate the total volume of water that would be trapped. Example: Input: terrain = [ [2, 3, 5, 1], [6, 5, 3, 4], [3, 1, 2, 5] ] Output: 7 Solution Approach # This problem can be effectively solved using a combination of Breadth-First Search (BFS) and a priority queue (Min-Heap). ...
Problem Statement # Given a grid of dimensions m x n, each cell in the grid can be either land (1) or water (0). You start at the top-left corner of the grid (0, 0) and can move either down or right at any point in time, but you can’t move through water. Find the number of unique paths from the top-left corner to the bottom-right corner (m-1, n-1). ...
Problem Statement # Given a binary tree, your goal is to install cameras on the tree nodes in such a way that every node in the tree is monitored. A camera at a node can monitor its parent, itself, and its immediate children. Calculate the minimum number of cameras needed to monitor all nodes of the given binary tree. Note: Every node has at most one parent. Tree nodes are numbered uniquely. ...
Problem Statement # Given two strings s1 and s2, return the minimum window in s1 which will contain all the characters in s2 in the order they appear in s2. If there is no such window in s1 that covers all characters in s2, return the empty string. If there are multiple such minimum-length windows, return the one with the left-most starting index. Solution Approach # The solution involves a two-pointer technique to explore all the substrings of s1 that could potentially cover s2 and then narrowing down to the one with minimum length that satisfies the condition. ...
Problem Statement # Design a class to calculate the median of a number stream at any time. The class should support two operations: addNum(int num) which adds an integer to the data structure, and findMedian() which returns the median of all elements so far. Solution Approach # The solution involves using two heaps: a max heap for the lower half of the numbers and a min heap for the upper half. ...
Problem Statement # Given a directed graph with n nodes labeled from 0 to n-1, and a list of edges where edges[i] = [ai, bi] represents a directed edge from node ai to node bi, determine if the graph contains a cycle. A cycle occurs if a node can be visited more than once by following the directed edges. Return true if the graph contains at least one cycle, otherwise return false. ...
Problem Statement # Given a weighted undirected graph with n vertices numbered from 0 to n-1, represented by an array edges where edges[i] = [from_i, to_i, weight_i] denotes a bidirectional and weighted edge between nodes from_i and to_i. Each node has a value values[i] representing its value. You start traversing the graph from node 0 and collect values. You can visit each node at most once. However, you can revisit node 0 any number of times. ...
Problem Statement # You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists. Your algorithm’s complexity must be better than brute force, meaning you can’t just check every possible range. Solution Approach # The solution involves using a min-heap to keep track of the minimum value across the k lists and expanding the range until it covers at least one number from each list. ...
Problem Statement # You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. The goal is to exactly reduce x to zero using the minimum number of operations, and return this number. If it is not possible, return -1. Solution Approach # The solution involves finding the longest subarray with the sum equal to totalSum - x (where totalSum is the sum of all elements in nums). ...
Problem Statement # Given a string s, return the sum of the number of unique characters in all substrings of s. In other words, you will be given a string and you need to sum up the total number of unique characters that appear in every possible substring of the string. Example: Input: s = “ABA” Output: 9 Explanation: The unique characters in all substrings are [“A”,“B”,“A”,“AB”,“BA”,“ABA”], with counts [1,1,1,2,2,2]. ...
Problem Statement # Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum is divisible by k. Example: Input: nums = [4,5,0,-2,-3,1], k = 5 Output: 7 Explanation: There are 7 subarrays with a sum divisible by 5: [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3], [4, 5, 0, -2, -3, 1]. Solution Approach # The solution involves using a hashmap to store the frequency of prefix sum mod k and applying the prefix sum technique. ...
Problem Statement # Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal. Example: Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4 Output: True Explanation: It’s possible to divide it into 4 subsets (5), (1, 4), (2, 3), (2, 3) with equal sums. Solution Approach # The solution involves using depth-first search (DFS) and backtracking to try and create k subsets with equal sums. ...
Problem Statement # Given an integer array nums, handle multiple queries of the following types: Update the value of an element in nums. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right. Implement the NumArray class: NumArray(int[] nums): Initializes the object with the integer array nums. void update(int index, int val): Updates the value of nums[index] to be val. int sumRange(int left, int right): Returns the sum of the elements of nums between indices left and right inclusive (i. ...
Problem Statement # Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and check the 10 most recent tweets in the user’s news feed. Functionalities: # postTweet(userId, tweetId): Compose a new tweet. getNewsFeed(userId): Retrieve the 10 most recent tweet IDs in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user themself. ...
Problem Statement # There is a special apple tree that grows several types of apples at different rates. The apples mature at different times, and they rot at different times after maturing. You are given two integer arrays apples and days, both of the same length. The i-th element of each array represents the number of apples that mature and the number of days they stay fresh, respectively, starting from the i-th day. ...
Problem Statement # There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints. In one step, you can take one card from the beginning or from the end of the row. You have k steps to take cards. Your score is the sum of the points of the cards you have taken. Given the integer array cardPoints and the integer k, return the maximum score you can obtain. ...
Problem Statement # You are given a list of songs where the i-th song has a duration of time[i] seconds. Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0. Example: Input: time = [30, 20, 150, 100, 40] Output: 3 Explanation: Three pairs have a total duration divisible by 60: (time[0] = 30, time[2] = 150): total duration 180 (time[1] = 20, time[3] = 100): total duration 120 (time[1] = 20, time[4] = 40): total duration 60 Solution Approach # The solution involves using a hashmap to keep track of the frequencies of song durations modulo 60. ...
Problem Statement # Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix. Example: Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 Output: 13 Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13. Solution Approach # The solution involves using a min heap to efficiently find the kth smallest element. ...
Problem Statement # A car travels from a starting position to a destination, a distance of target miles. There are gas stations along the way. The car starts with an initial tank of fuel, and it can travel startFuel miles on a full tank. You are given an integer target, an integer startFuel, and an array stations where stations[i] = [position_i, fuel_i] indicates that the i-th gas station is position_i miles along the way and has fuel_i liters of gas. ...
Problem Statement # Given a m x n grid filled with non-negative numbers, find a path from the top left to the bottom right corner, which maximizes the sum of the numbers along its path. You can only move either down or right at any point in time. Example: Input: grid = [[1,3,1], [1,5,1], [4,2,1]] Output: 12 Explanation: The path 1 -> 3 -> 5 -> 1 -> 1 -> 1 maximizes the sum. ...
Problem Statement # Given a circular integer array nums (the last element is connected to the first element), find the maximum possible sum of a non-empty subarray of nums. Example: Input: nums = [5, -3, 5] Output: 10 Explanation: Subarray [5, 5] has maximum sum 5 + 5 = 10. Solution Approach # The solution involves finding the maximum subarray sum using Kadane’s algorithm. Since the array is circular, the maximum sum may wrap around the end of the array. ...
Problem Statement # Given an undirected, connected tree with n nodes labeled from 0 to n - 1, and an array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi, return an array answer of length n where answer[i] is the sum of the distances between the i-th node and all other nodes. Example: Input: n = 6, edges = [[0,1], [0,2], [2,3], [2,4], [2,5]] Output: [8, 12, 6, 10, 10, 10] Explanation: The tree is shown as follows: 0 / 1 2 /| ...
Problem Statement # Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s. Strings consist of lowercase English letters only and the order of output does not matter. Example: Input: s = “cbaebabacd”, p = “abc” Output: [0, 6] Explanation: The substring with start index = 0 is “cba”, which is an anagram of “abc”. The substring with start index = 6 is “bac”, also an anagram of “abc”. ...
Problem # Given an array nums and an integer k, find the maximum sum of non-overlapping subarrays, each of size k. Example: Input: nums = [1, 2, 3, 4, 5, 6, 1], k = 2 Output: 15 Explanation: The maximum sum is obtained by taking subarrays [5, 6] and [3, 4], which sum to 11 and 4 respectively. The total is 15. Solution Approach # The solution involves using a sliding window approach to find the maximum sum of each subarray of size k, and dynamic programming to ensure non-overlapping. ...
Problem # Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from each other. If it is not possible to rearrange the string, return an empty string. Example: Input: s = “aabbcc”, k = 3 Output: “abcabc” or “bacbac” Explanation: The same characters are at least distance 3 from each other. Solution Approach # The solution involves using a max heap to ensure the most frequent characters are placed first. ...
Problem # Given an array of integers nums, find the length of the longest subarray whose sum is zero. Example: Input: nums = [2, -2, 3, 0, 4, -7] Output: 4 Explanation: The longest zero-sum subarray is [3, 0, 4, -7]. Solution Approach # The solution involves using a hashmap to store the cumulative sum up to each index. If the same cumulative sum occurs again, it means that the subarray between these indices sums to zero. ...
Problem # Given an integer array nums, find three numbers whose product is maximum and return the maximum product. Example: Input: nums = [-1, -2, -3, 4] Output: 24 Explanation: The maximum product is obtained by multiplying -3 * -2 * 4 = 24. Solution Approach # The solution involves finding the three largest numbers and the two smallest numbers in the array. The maximum product can be obtained either by multiplying the three largest numbers or by multiplying the two smallest numbers (which could be negative and thus make a positive product when multiplied together) with the largest number. ...
Problem # Given a network represented as a graph with n nodes labeled from 0 to n-1 and an array connections where connections[i] = [a, b] indicates that there is a bidirectional road between nodes a and b, your task is to find the node that, if removed, would minimize the connectivity of the network. The connectivity of a network is defined as the number of nodes that are reachable from any node. ...
Problem # Given the head of a sorted linked list, delete all nodes that have duplicate numbers (leaving only distinct numbers from the original list) and return the sorted list. Example: Input: head = [1, 2, 3, 3, 4, 4, 5] Output: [1, 2, 5] Solution Approach # The solution involves using two pointers, one to iterate through the list (current) and another to ensure the connection between non-duplicate nodes (prev). ...
Problem # Given a string s consisting of only two characters A and B, find the length of the longest substring that contains an equal number of As and Bs. Example: # Input: s = "ABABBAABB" Output: 8 (The longest balanced substring is “ABABBAAB”) Solution Approach: # The solution involves using a hash map to keep track of the counts of As and Bs and their differences at each index. ...
Problem # Given an array nums of integers which is initially increasing and then decreasing, find a peak element. A peak element is an element which is greater than its neighbors. Assume that nums[-1] and nums[n] (elements outside the array) are negative infinity. Example: Input: nums = [1, 3, 20, 4, 1, 0] Output: 20 Solution Approach # The solution involves using a modified binary search. Since the array is initially increasing and then decreasing, a peak element can be found where the trend changes from increasing to decreasing. ...
Problem # Given an array of non-negative integers nums and an integer k, find if the array has a continuous subarray of size at least two that sums up to a multiple of k. Example: Input: nums = [23, 2, 4, 6, 7], k = 6 Output: True Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6. Solution Approach # The solution uses a hashmap to store the remainder of the cumulative sum modulo k and their indices. ...
Problem # You are given a 2D grid map of '1's (land) and '0's (water). An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water. Write an algorithm to find the perimeter of the island in the grid. If there are multiple islands, calculate the perimeter of the largest one. ...
Problem # Given an array nums and a non-negative integer k, rotate the array to the right by k steps. Each step involves moving the last element of the array to the front. Example: Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3 Output: [5, 6, 7, 1, 2, 3, 4] Solution Approach # The solution involves reversing parts of the array. First, reverse the entire array, then reverse the first k elements, and finally reverse the remaining n-k elements. ...
Problem # Given an array of integers nums, find the maximum difference between any two elements nums[j] and nums[i] such that j > i. Example: Input: nums = [7, 1, 5, 4] Output: 4 Explanation: The maximum difference is between 5 and 1. Solution Approach # The solution involves iterating through the array while keeping track of the minimum element found so far and the maximum difference. Algorithm Steps # Initialize two variables: min_element to the first element and max_diff to 0. ...
Problem # Given a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between). Example: Input: 3 / \ 9 20 / \ 15 7 Output: [[3], [20, 9], [15, 7]] Solution Approach # The solution uses a breadth-first search (BFS) approach with a queue, alternating the direction of traversal with each level of the tree. ...
Problem # Given an array of integers nums, find the length of the longest subarray where the sum of the first half of the subarray is equal to the sum of the second half of the subarray. If no such subarray exists, return 0. Example: Input: nums = [1, 2, 3, 0, 3, 2, 1] Output: 6 (The subarray [1, 2, 3, 0, 3, 2] has a balanced sum) Constraints: ...
Problem # Given an array of integers nums and two integers x and y, find the length of the longest contiguous subarray where the number of occurrences of x is equal to the number of occurrences of y. Example: Input: nums = [1, 2, 2, 3, 1, 1, 3], x = 1, y = 3 Output: 6 Explanation: The longest subarray with equal occurrences of 1 and 3 is [2, 2, 3, 1, 1, 3]. ...
Problem # Given a binary array data, your task is to find the minimum number of swaps required to group all 1’s present in the array together in any place in the array. Example: Input: data = [1, 0, 1, 0, 1] Output: 1 Explanation: One of the ways to group all 1’s together is [1, 1, 1, 0, 0], which can be achieved by 1 swap. Solution Approach # The solution involves using a sliding window approach. ...
Problem # Given an array nums, for each element, find the next greater element within the array. The next greater element for an element x is the first greater element on the right side of x in the array. If it does not exist, output -1 for this element. Example: Input: nums = [2, 1, 3, 5, 6, 4] Output: [3, 3, 5, 6, -1, -1] Solution # The solution involves using a stack to efficiently find the next greater element for each element in the array. ...
Problem # Given two sorted linked lists, merge them into one sorted list. The new list should be made by splicing together the nodes of the first two lists. Example: Input: list1 = [1, 2, 4], list2 = [1, 3, 4] Output: [1, 1, 2, 3, 4, 4] Solution # The solution involves using a two-pointer technique. Create a new linked list and add nodes to it by comparing the current nodes of the two lists, advancing the pointer of the list with the smaller current node. ...
Problem # You are given an array arr of positive integers, representing the maximum number of jumps you can make from each index. You start from the first index and must reach the last index. Find the minimum number of jumps required to reach the end of the array. Solution # To solve this problem, we can use dynamic programming (DP). We will create a new DP array dp and initialize it with infinity except for the first element, which is set to 0. ...
Problem # Given an array of integers nums and a target value k, find the length of the shortest subarray whose sum is greater than or equal to k. Solution # Steps: Initialize two pointers, left and right, both at the beginning of the array. Initialize a variable current_sum to 0. Iterate while right is within the bounds of the array: Add nums[right] to current_sum. While current_sum is greater than or equal to k: Update the minimum length if needed: min_length = min(min_length, right - left + 1). ...
Problem # Given a binary tree where each node can either be 0 or 1, each root-to-leaf path represents a binary number. A leaf is a node with no children. The root is the top node of the tree. Calculate the sum of these numbers. Example: # Input: 1 / \ 0 1 / \ / \ 0 1 0 1 Output: 22 Explanation: The binary numbers are 100, 101, 110, and 111, which sum to 22. ...
Problem # Given an array of positive integers, find the maximum sum of non-adjacent elements in the array. Example: # Input: nums = [3, 2, 7, 10] Output: 13 Explanation: The maximum sum is obtained by taking elements 3 and 10. Input: nums = [3, 2, 5, 10, 7] Output: 15 Explanation: The maximum sum is obtained by taking elements 3, 5, and 7. Solution Approach # This problem can be solved using dynamic programming. ...