Prefix Sum

A collection of 28 posts

Perfect Rectangle Solution In C++/Java/Python/JS

Given an array rectangles where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (xi, yi) and the top-right point of it is (ai, bi). Return true if all the rectangles together form an exact cover of a rectangular region. Example Input:

Rectangle Area II Solution In C++/Java/Python/JS

Problem Description You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] denotes the ith rectangle where (xi1, yi1) are the coordinates of the bottom-left corner, and (xi2, yi2) are the coordinates of the top-right corner. Calculate the total area covered by all rectangles

Prefix Sum

Number of Flowers in Full Bloom Solution In C++/Java/Python/JS

Problem Description You are given a 0-indexed 2D integer array flowers, where flowers[i] = [start i, end i] means the ith flower will be in full bloom from start i to end i (inclusive). You are also given a 0-indexed integer array people of size n, where people[i] is

Prefix Sum

Minimum Cost to Make Array Equal Solution In C++/Java/Python/JS

Problem Description You are given two 0-indexed arrays nums and cost consisting each of  n positive integers. You can do the following operation any number of times: * Increase or decrease any element of the array nums by 1. The cost of doing one operation on the ith element is cost[

Count Vowel Strings in Ranges Solution In C++/Java/Python/JS

Problem Description You are given a 0-indexed array of strings words and a 2D array of integers queries. Each query queries[i] = [li, ri] asks us to find the number of strings present at the indices ranging from li to ri (both inclusive) of words that start and end with

Prefix Sum

Left and Right Sum Differences

Problem Description Given a 0-indexed integer array nums, find a 0-indexed integer array answer where: 1) answer.length == nums.length. 2) answer[i] = |leftSum[i] - rightSum[i]|. Where: 1) leftSum[i] is the sum of elements to the left of the index i in the array nums. If there

My Calendar II

Problem Description You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking. A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.

Shifting Letters II

Problem Description You are given a string s of lowercase English letters and a 2D integer array shifts where shifts[i] = [start i, end i, direction i]. For every i, shift the characters in s from the index start i to the index end i (inclusive) forward if direction i

Car Pooling

Problem Description There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west). You are given the integer capacity and an array trips where trips[i] = [numPassengers i, from i, to i] indicates that the ith trip has numPassengers

Pongal Bunk

Problem Description Given a number N, which is the size of array where indices are from 1 to N . Initially all the elements of array are 0 . Q queries are given . Each query contains two variables L and R . For each query you have to perform the following operation: for

Points That Intersect With Cars

Problem Description You are given a 0-indexed 2D integer array nums representing the coordinates of the cars parking on a number line. For any index i, nums[i] = [start i, end i] where start i is the starting point of the ith car and end i is the ending point

Maximum Population Year

Problem Description You are given a 2D integer array logs where each  logs[i] = [birth i, death i] indicates the birth and death years of the ith person. The population of some year x is the number of people alive during that year. The ith person is counted in year

Count Number of Nice Subarrays Solution In C++/Python/java/JS

Problem Description: Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it. Return the number of nice sub-arrays. Examples: Input: nums = [1,1,2,1,1], k = 3 Output: 2 Explanation: The only sub-arrays with 3

Find All Good Indices

Problem Description You are given a 0-indexed integer array nums of size n and a positive integer k.We call an index i in the range k <= i < n - k good if the following conditions are satisfied: 1. The k elements that are just before the index

Movement of Robots

Problem Description Some robots are standing on an infinite number line with their initial coordinates given by a 0-indexed integer array nums and will start moving once given the command to move. The robots will move a unit distance each second. You are given a string s denoting the direction

Count of Interesting Subarrays

Problem Description: You are given a 0-indexed integer array nums, an integer modulo, and an integer k. Your task is to find the count of subarrays that are interesting. A subarray nums[l..r] is interesting if the following condition holds: Let cnt be the number of indices i in

Continuous Subarray Sum

Problem Description: Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise. A good subarray is a subarray where: its length is at least two, and the sum of the elements of the subarray is a multiple of k. Examples:

Count Number of Bad Pairs Solution In C++/Java/Python/JS

Problem Description: You are given a 0-indexed integer array nums. A pair of indices (i, j) is a bad pair if i < j and j - i ≠ nums[j] - nums[i]. Return the total number of bad pairs in nums. Examples: Input: nums = [4, 1, 3, 3] Output:

Product of the Last K Numbers

Design an algorithm that accepts a stream of integers and retrieves the product of the last k integers of the stream. Implement the ProductOfNumbers class: ProductOfNumbers() Initializes the object with an empty stream. void add(int num) Appends the integer num to the stream. int getProduct(int k) Returns the

Removing Minimum Number of Magic Beans

Problem Description You are given an array of positive integers beans, where each integer represents the number of magic beans found in a particular magic bag. Remove any number of beans (possibly none) from each bag such that the number of beans in each remaining non-empty bag (still containing at

Make Sum Divisible by P

Problem Description Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array. Return the length of the smallest subarray that you need to remove, or -1

Subarray Sums Divisible by K

Problem Description: Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k. A subarray is a contiguous part of an array. Examples: Input: nums = [4,5,0,-2,-3,1], k = 5 Output: 7 Explanation: There are 7

Find Good Days to Rob the Bank

Problem Description: You and a gang of thieves are planning on robbing a bank. You are given a 0-indexed integer array security, where security[i] is the number of guards on duty on the ith day. The days are numbered starting from 0. You are also given an integer time.

Sum of Absolute Differences in a Sorted Array

Problem Description You are given an integer array nums sorted in non-decreasing order. Build and return an integer array result with the same length as nums such that result[i] is equal to the summation of absolute differences between nums[i] and all the other elements in the array. In

Product of Array Except Self

Problem Description Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an