Counting Non Overlapping Pairs

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.

Join the 1M+ learners on CodeSignal

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

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)

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)
      }
    }
  }

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
}

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
}

Introduction

Task Statement

Understanding the Solution: The Idea

Join the 1M+ learners on CodeSignal

Solution Building: Step 1

Solution Building: Step 2

Solution Building: Step 3

Lesson Summary