Scale Engineer

Count Almost Equal Pairs I

Med
#2898Time: O(N^2 * D), where N is the length of the `nums` array and D is the maximum number of digits in a number. The two nested loops result in O(N^2) pairs. For each pair, the `isAlmostEqual` function takes O(D) time for string conversion and comparison.Space: O(D), where D is the maximum number of digits. This space is used by the helper function to store the indices of differing characters.1 company
Patterns
CountingEnumeration
Algorithms
Sorting
Data structures
ArrayHash Table
Companies
Info Edge

Prompt

You are given an array nums consisting of positive integers.

We call two integers x and y in this problem almost equal if both integers can become equal after performing the following operation at most once:

  • Choose either x or y and swap any two digits within the chosen number.

Return the number of indices i and j in nums where i < j such that nums[i] and nums[j] are almost equal.

Note that it is allowed for an integer to have leading zeros after performing an operation.

 

Example 1:

Input: nums = [3,12,30,17,21]

Output: 2

Explanation:

The almost equal pairs of elements are:

  • 3 and 30. By swapping 3 and 0 in 30, you get 3.
  • 12 and 21. By swapping 1 and 2 in 12, you get 21.

Example 2:

Input: nums = [1,1,1,1,1]

Output: 10

Explanation:

Every two elements in the array are almost equal.

Example 3:

Input: nums = [123,231]

Output: 0

Explanation:

We cannot swap any two digits of 123 or 231 to reach the other.

 

Constraints:

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 106

Approaches

2 approaches with complexity analysis and trade-offs.

This straightforward approach involves checking every possible pair of numbers in the array to see if they are almost equal.

Algorithm

  1. Initialize a counter count to 0.
  2. Use a nested loop to iterate through every pair of indices (i, j) such that i < j.
  3. For each pair, call a helper function isAlmostEqual(nums[i], nums[j]).
  4. If the helper function returns true, increment count.
  5. After checking all pairs, return count.

Helper isAlmostEqual(x, y):

  1. Convert x and y to strings s1 and s2.
  2. If their lengths are different, return false.
  3. Find all indices where s1 and s2 differ.
  4. If there are 0 differing indices, they are equal, return true.
  5. If there are 2 differing indices, say d1 and d2, check if s1[d1] == s2[d2] and s1[d2] == s2[d1]. If true, return true.
  6. Otherwise, return false.

Walkthrough

The algorithm uses two nested loops to iterate through all unique pairs of indices (i, j) where i < j. For each pair of numbers (nums[i], nums[j]), a helper function isAlmostEqual is invoked. This function determines if one number can be transformed into the other by at most one swap of digits. It does this by converting the numbers to strings and comparing them. If the strings are identical (zero swaps), they are almost equal. If they differ, the function counts the number of positions with different characters. If there are exactly two differing positions, it verifies if these characters are swapped between the two strings. If this condition holds, the pair is considered almost equal (one swap). A counter is incremented for every almost equal pair found.

class Solution {    public int countAlmostEqualPairs(int[] nums) {        int n = nums.length;        int count = 0;        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                if (isAlmostEqual(nums[i], nums[j])) {                    count++;                }            }        }        return count;    }     private boolean isAlmostEqual(int x, int y) {        String s1 = String.valueOf(x);        String s2 = String.valueOf(y);         if (s1.length() != s2.length()) {            return false;        }         java.util.List<Integer> diffIndices = new java.util.ArrayList<>();        for (int i = 0; i < s1.length(); i++) {            if (s1.charAt(i) != s2.charAt(i)) {                diffIndices.add(i);            }        }         if (diffIndices.isEmpty()) {            return true; // The numbers are equal        }         if (diffIndices.size() == 2) {            int i = diffIndices.get(0);            int j = diffIndices.get(1);            return s1.charAt(i) == s2.charAt(j) && s1.charAt(j) == s2.charAt(i);        }         return false;    }}

Complexity

Time

O(N^2 * D), where N is the length of the `nums` array and D is the maximum number of digits in a number. The two nested loops result in O(N^2) pairs. For each pair, the `isAlmostEqual` function takes O(D) time for string conversion and comparison.

Space

O(D), where D is the maximum number of digits. This space is used by the helper function to store the indices of differing characters.

Trade-offs

Pros

  • Simple to understand and implement.

  • Works well for the given constraints due to the small size of N.

Cons

  • Inefficient for larger input sizes as its time complexity is quadratic.

Solutions

class Solution {public  int countPairs(int[] nums) {    Arrays.sort(nums);    int ans = 0;    Map<Integer, Integer> cnt = new HashMap<>();    for (int x : nums) {      Set<Integer> vis = new HashSet<>();      vis.add(x);      char[] s = String.valueOf(x).toCharArray();      for (int j = 0; j < s.length; ++j) {        for (int i = 0; i < j; ++i) {          swap(s, i, j);          vis.add(Integer.parseInt(String.valueOf(s)));          swap(s, i, j);        }      }      for (int y : vis) {        ans += cnt.getOrDefault(y, 0);      }      cnt.merge(x, 1, Integer : : sum);    }    return ans;  }private  void swap(char[] s, int i, int j) {    char t = s[i];    s[i] = s[j];    s[j] = t;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem