Count Number of Bad Pairs — LeetCode 2364 Python Solution
MediumArrayHash TableMathCounting
- Problem
- #2364
- Pattern
- Math and Number Theory
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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].
Example
- Input
- nums = [4,1,3,3]
- Output
- 5
- Explanation
- The pair (0, 1) is a bad pair since 1 - 0 != 1 - 4.
Python solution
Python
class Solution:
def countBadPairs(self, nums: List[int]) -> int:
cnt = Counter()
ans = 0
for i, x in enumerate(nums):
ans += i - cnt[i - x]
cnt[i - x] += 1
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n), where n is the length of the array \textit{nums} auxiliary |
Pattern: Math and Number Theory
Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 2364. Count Number of Bad Pairs is filed here because LeetCode tags it Math, which is the vocabulary this hub collects.
The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.
Related problems
LeetCode 914X of a Kind in a Deck of CardsEasyLeetCode 1512Number of Good PairsEasyLeetCode 1814Count Nice Pairs in an ArrayMediumLeetCode 1994The Number of Good SubsetsHardLeetCode 2001Number of Pairs of Interchangeable RectanglesMediumLeetCode 2442Count Number of Distinct Integers After Reverse OperationsMedium
Frequently asked questions
- How hard is LeetCode 2364. Count Number of Bad Pairs?
- LeetCode 2364. Count Number of Bad Pairs is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2364. Count Number of Bad Pairs?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2364. Count Number of Bad Pairs?
- The Python solution on this page uses O(n), where n is the length of the array \textit{nums} auxiliary space.
- What topics does LeetCode 2364. Count Number of Bad Pairs cover?
- LeetCode 2364. Count Number of Bad Pairs is tagged Array, Hash Table, Math and Counting on LeetCode.