Counting Non Overlapping Pairs | CodeSignal Learn

Counting Non Overlapping Pairs | CodeSignal Learn

Introduction

Hello, coding enthusiast! In our journey to master coding and problem-solving, we've arrived at an interesting challenge today. We're going to focus heavily on combinatorial problems in practice. Specifically, we're examining combinatorial problems that involve working with large data sets and multiple pairs of numbers. We'll learn how to solve significant problems efficiently by making smart use of data structures like mutable maps and sidestepping expensive operations like iterating over large arrays. Are you ready? Let's dive in!

Task Statement

In this unit's task, you'll be given a large array composed of pairs of distinct, positive integers, including up to 1,000,000 elements. Your challenge is to write a Scala function to count the number of ordered index pairs (i, j) (i != j) where the i -th pair does not share a common element with the j -th pair. A crucial point to remember is that a pair (a, b) is considered identical to (b, a), meaning the order of elements in a pair is irrelevant in this case. It is guaranteed that no two pairs are element-wise equal. For example, given the array Array(Array(2, 5), Array(1, 6), Array(3, 2), Array(4, 2), Array(5, 1), Array(6, 3)), the output should be 8 . The required index pairs are the following: (0, 1) (i.e., the pair [2, 5] does not share a common element with the pair [1, 6]), (0, 5) ([2, 5] does not share a common element with [6, 3]), (1, 2), (1, 3), (2, 4), (3, 4), (3, 5), (4, 5) .

Understanding the Solution: The Idea

At the core of our solution, we're going to leverage the power of combinatorics and a smart way of keeping track of occurrences to solve this problem efficiently. The central idea is to calculate the total number of ordered index pairs and then subtract from this total the number of pairs that share a common element. This will leave us with the count of pairs that do not share a common element, which is what we're after. First, we will calculate the total number of ordered index pairs possible in the array. In a set of n pairs, the number of ordered pairs (i, j) with i != j is given by the formula n * (n - 1) . This is because each element in the set can pair with every other element, and the order of indices matters. Second, we'll count the number of ordered index pairs that have at least one common element. To do this, we will use a mutable map to track each number's appearance in the pairs. For each number, we calculate how many pairs it appears in and sum these numbers up.

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Solution Building: Step 1

Let's begin with the initial steps of our solution. The first thing we need is a convenient place to store the occurrence of each number in the pairs. Here, Scala's mutable map data structure shines. It enables us to efficiently track the number and its corresponding occurrences. Next, we calculate the total number of ordered index pairs using the formula n * (n - 1) . We'll need this for our final calculation. Let's initialize an empty mutable map and calculate the total pairs. import scala.collection.mutable def nonCommonPairs(arr: Array[Array[Int]]): Int = {val indices = mutable.Map[Int, mutable.ListBuffer[Int]]() val n = arr.length val totalPairs = n * (n - 1)

Solution Building: Step 2

With the first step completed, our next move is to populate the indices mutable map by iterating over the array of pairs. For each pair, we'll examine its two elements and either append the current index to the list of indices for this number (if it’s already in the map) or start a new list for it (if it isn't). Here's how we modify our function to carry out this operation: import scala.collection.mutable def nonCommonPairs(arr: Array[Array[Int]]): Int = {val indices = mutable.Map[Int, mutable.ListBuffer[Int]]() val n = arr.length val totalPairs = n * (n - 1) for ((pair, idx) <- arr.zipWithIndex) {for (num <- pair) {if (indices.contains(num)) {indices(num) += idx} else {indices(num) = mutable.ListBuffer(idx)}}}

Solution Building: Step 3

Finally, with all the data in place, we arrive at our final step of calculation. We need to calculate the total number of ordered index pairs that share at least one common element. For that, we'll consider each number in the array and count the number of times those numbers occur in different pairs. For each number, if it appears in k pairs, then there are k * (k - 1) ordered pairs of indices that share this number. Finally, we subtract these common pairs from the total pairs to get our answer — the count of pairs without a common number. Adding this last part to our function gives us the solution: import scala.collection.mutable def nonCommonPairs(arr: Array[Array[Int]]): Int = {val indices = mutable.Map[Int, mutable.ListBuffer[Int]]() val n = arr.length val totalPairs = n * (n - 1) for ((pair, idx) <- arr.zipWithIndex) {for (num <- pair) {if (indices.contains(num)) {indices(num) += idx} else {indices(num) = mutable.ListBuffer(idx)}}} val commonPairs = indices.values.map(list => list.size * (list.size - 1)).sum totalPairs - commonPairs}

Scala

import scala.collection.mutable

def nonCommonPairs(arr: Array[Array[Int]]): Int = {
  val indices = mutable.Map[Int, mutable.ListBuffer[Int]]()
  val n = arr.length
  val totalPairs = n * (n - 1)

Scala

import scala.collection.mutable

def nonCommonPairs(arr: Array[Array[Int]]): Int = {
  val indices = mutable.Map[Int, mutable.ListBuffer[Int]]()
  val n = arr.length
  val totalPairs = n * (n - 1)

  for ((pair, idx) <- arr.zipWithIndex) {
    for (num <- pair) {
      if (indices.contains(num)) {
        indices(num) += idx
      } else {
        indices(num) = mutable.ListBuffer(idx)
      }
    }
  }

Scala

import scala.collection.mutable

def nonCommonPairs(arr: Array[Array[Int]]): Int = {
  val indices = mutable.Map[Int, mutable.ListBuffer[Int]]()
  val n = arr.length
  val totalPairs = n * (n - 1)

  for ((pair, idx) <- arr.zipWithIndex) {
    for (num <- pair) {
      if (indices.contains(num)) {
        indices(num) += idx
      } else {
        indices(num) = mutable.ListBuffer(idx)
      }
    }
  }

  val commonPairs = indices.values.map(list => list.size * (list.size - 1)).sum

  totalPairs - commonPairs
}