Count Largest Equal Pairs

Count Largest Equal Pairs

Count Largest Equal Pairs

Category: algorithms

Description

Given a 0-indexed integer array nums of length n, return the number of pairs (i, j) where 0 <= i <= j < n, such that nums[i] == nums[j] and nums[k] <= nums[i] for i <= k <= j

Solutions

The O(N^2) solution is simple as we traverse every pair and keep track of the maximum value between them, thus, we count pairs where the maximum between the pairs is less than or equal to the equal pair.

But the constraints of the problems won't allow O(N^2), to optimize we make use of the fact that we are only interested in indexes such that the maximum up to that index is at most nums[i] for each i, ie. if j is the first index to the right of i such that nums[j] > nums[i] then we only need to count equal pairs from index i to index j - 1.

So, we need the next greater element for each index, which is a well-known monotonic stack problem possible in O(N) https://leetcode.com/problems/next-greater-element-ii/

Now we need to count the frequency of arr[i] from index i to next_greater[i] - 1 for each i, this is also a well-known technique, range frequency queries, https://leetcode.com/problems/range-frequency-queries/

Using both these techniques, the overall solution is O(N log N) which is suitable with given constraints.

The question can be changed to only count pairs with i < j instead of i <= j as (i, i) is always counted anyways, thus we just subtract N from the below solution for that.

Here's the optimal code with a brute force checker function and random test case generator to verify solutions.

https://leetcode.com/playground/4BT2WGhq

Test Cases

Input: nums = [4, 2, 4, 5, 4]

Output: 6

Input: nums = [3, 4, 4, 3, 4]

Output: 8

Tags

Monotonic Stack, Binary Search

Comments

Post a Comment

Popular posts from this blog

Range Update Maximum Query

Range Update Maximum Query Range Update Maximum Query Problem Description You are given an integer array nums and a list of queries queries , where each query queries[i] is of the form [left, right, M] . Each query represents an update operation that modifies elements in nums between indices left and right (inclusive). The update sets nums[i] = max(nums[i], M) for left <= i <= right . Your task is to return the array nums after applying all the update queries. Problem Analysis The given problem involves multiple range updates and then point queries. It is a combination of several programming concepts, including small-to-large merging, offline queries, and sweep line. This problem is not commonly found and requires a novel approach to solve. The time complexity of the solution is not immediately obvious and requires a proof to understand. Therefore, this problem can be classified as hard, as the alternative solutions also involve implementing not-so-common a...
Read more

Exploring a Number Conversion Algorithm

Exploring a Number Conversion Algorithm Exploring a Number Conversion Algorithm Category: algorithms Description In this blog post, we will explore an interesting number conversion algorithm that utilizes the Counter data structure from the collections module. We will walk through the provided code snippet and understand its functionality. Code Snippet from collections import Counter def convert(n): if n <= 0: return Counter() x = 1 while pow(x + 1, x + 1) <= n: x += 1 return convert(n - pow(x, x)) + Counter({x: 1}) print(convert(38748358348)) Explanation The code begins by importing the Counter class from the collections module. The Counter class is a powerful tool for counting elements in an iterable. It allows us to easily keep track of the frequency of elements in a collection. The convert function takes an integer n as input and returns a Counter object. Let's dive into the implementation of the convert function: def conv...
Read more

Toeplitz Matrix

Image
Given an m x n matrix , return  true  if the matrix is Toeplitz. Otherwise, return false . A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.   Example 1: Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]] Output: true Explanation: In the above grid, the diagonals are: "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]". In each diagonal all elements are the same, so the answer is True. Example 2: Input: matrix = [[1,2],[2,2]] Output: false Explanation: The diagonal "[1, 2]" has different elements.   Constraints: m == matrix.length n == matrix[i].length 1 <= m, n <= 20 0 <= matrix[i][j] <= 99   Follow up: What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once? What if the matrix is so large ...
Read more