Java Combinatorial Pair Counting

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 datasets and multiple pairs of numbers. We'll learn how to solve significant problems efficiently by implementing smart use of data structures like HashMap and sidestepping expensive operations like iterating over large arrays. Are you ready? Let's dive in!

Task Statement

i \ne j

Understanding the Solution: The Idea

n \cdot (n - 1) / 2

Join the 1M+ learners on CodeSignal

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

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class NonCommonPairs {
    public static int nonCommonPairs(List<Map.Entry<Integer, Integer>> arr) {
        Map<Integer, List<Integer>> indices = new HashMap<>();
        int totalPairs = arr.size() * (arr.size() - 1) / 2;
        
        // (The rest of the code will be added in subsequent steps)
        return totalPairs; // Temporary return to avoid compilation error
    }

    public static void main(String[] args) {
        // Code for testing will be added later
    }
}

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class NonCommonPairs {
    public static int nonCommonPairs(List<Map.Entry<Integer, Integer>> arr) {
        Map<Integer, List<Integer>> indices = new HashMap<>();
        int totalPairs = arr.size() * (arr.size() - 1) / 2;
        
        for (int idx = 0; idx < arr.size(); ++idx) {
            Map.Entry<Integer, Integer> pair = arr.get(idx);
            for (int num : new int[]{pair.getKey(), pair.getValue()}) {
                indices.computeIfAbsent(num, k -> new ArrayList<>()).add(idx);
            }
        }
        
        // (The rest of the code will be added in the next step)
        return totalPairs; // Temporary return to avoid compilation error
    }

    public static void main(String[] args) {
        // Code for testing will be added later
    }
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class NonCommonPairs {
    public static int nonCommonPairs(List<Map.Entry<Integer, Integer>> arr) {
        Map<Integer, List<Integer>> indices = new HashMap<>();
        int totalPairs = arr.size() * (arr.size() - 1) / 2;
        
        for (int idx = 0; idx < arr.size(); ++idx) {
            Map.Entry<Integer, Integer> pair = arr.get(idx);
            for (int num : new int[]{pair.getKey(), pair.getValue()}) {
                indices.computeIfAbsent(num, k -> new ArrayList<>()).add(idx);
            }
        }
        
        // (The rest of the code will be added in the next step)
        return totalPairs; // Temporary return to avoid compilation error
    }

    public static void main(String[] args) {
        // Code for testing will be added later
    }
}

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.AbstractMap.SimpleEntry;

public class NonCommonPairs {
    public static int nonCommonPairs(List<Map.Entry<Integer, Integer>> arr) {
        Map<Integer, List<Integer>> indices = new HashMap<>();
        int totalPairs = arr.size() * (arr.size() - 1) / 2;
        
        for (int idx = 0; idx < arr.size(); ++idx) {
            Map.Entry<Integer, Integer> pair = arr.get(idx);
            for (int num : new int[]{pair.getKey(), pair.getValue()}) {
                indices.computeIfAbsent(num, k -> new ArrayList<>()).add(idx);
            }
        }

        int commonPairs = 0;
        for (Map.Entry<Integer, List<Integer>> entry : indices.entrySet()) {
            int size = entry.getValue().size();
            commonPairs += size * (size - 1) / 2;
        }
        
        return totalPairs - commonPairs;
    }

    public static void main(String[] args) {
        List<Map.Entry<Integer, Integer>> arr = new ArrayList<>();
        arr.add(new SimpleEntry<>(2, 5));
        arr.add(new SimpleEntry<>(1, 6));
        arr.add(new SimpleEntry<>(3, 2));
        arr.add(new SimpleEntry<>(4, 2));
        arr.add(new SimpleEntry<>(5, 1));
        arr.add(new SimpleEntry<>(6, 3));
        
        System.out.println("Count of non-common pairs: " + nonCommonPairs(arr));
    }
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.AbstractMap.SimpleEntry;

public class NonCommonPairs {
    public static int nonCommonPairs(List<Map.Entry<Integer, Integer>> arr) {
        Map<Integer, List<Integer>> indices = new HashMap<>();
        int totalPairs = arr.size() * (arr.size() - 1) / 2;
        
        for (int idx = 0; idx < arr.size(); ++idx) {
            Map.Entry<Integer, Integer> pair = arr.get(idx);
            for (int num : new int[]{pair.getKey(), pair.getValue()}) {
                indices.computeIfAbsent(num, k -> new ArrayList<>()).add(idx);
            }
        }

        int commonPairs = 0;
        for (Map.Entry<Integer, List<Integer>> entry : indices.entrySet()) {
            int size = entry.getValue().size();
            commonPairs += size * (size - 1) / 2;
        }
        
        return totalPairs - commonPairs;
    }

    public static void main(String[] args) {
        List<Map.Entry<Integer, Integer>> arr = new ArrayList<>();
        arr.add(new SimpleEntry<>(2, 5));
        arr.add(new SimpleEntry<>(1, 6));
        arr.add(new SimpleEntry<>(3, 2));
        arr.add(new SimpleEntry<>(4, 2));
        arr.add(new SimpleEntry<>(5, 1));
        arr.add(new SimpleEntry<>(6, 3));
        
        System.out.println("Count of non-common pairs: " + nonCommonPairs(arr));
    }
}

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class NonCommonPairs {
    public static int nonCommonPairs(List<Map.Entry<Integer, Integer>> arr) {
        Map<Integer, List<Integer>> indices = new HashMap<>();
        int totalPairs = arr.size() * (arr.size() - 1) / 2;
        
        // (The rest of the code will be added in subsequent steps)
        return totalPairs; // Temporary return to avoid compilation error
    }

    public static void main(String[] args) {
        // Code for testing will be added later
    }
}

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class NonCommonPairs {
    public static int nonCommonPairs(List<Map.Entry<Integer, Integer>> arr) {
        Map<Integer, List<Integer>> indices = new HashMap<>();
        int totalPairs = arr.size() * (arr.size() - 1) / 2;
        
        for (int idx = 0; idx < arr.size(); ++idx) {
            Map.Entry<Integer, Integer> pair = arr.get(idx);
            for (int num : new int[]{pair.getKey(), pair.getValue()}) {
                indices.computeIfAbsent(num, k -> new ArrayList<>()).add(idx);
            }
        }
        
        // (The rest of the code will be added in the next step)
        return totalPairs; // Temporary return to avoid compilation error
    }

    public static void main(String[] args) {
        // Code for testing will be added later
    }
}

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.AbstractMap.SimpleEntry;

public class NonCommonPairs {
    public static int nonCommonPairs(List<Map.Entry<Integer, Integer>> arr) {
        Map<Integer, List<Integer>> indices = new HashMap<>();
        int totalPairs = arr.size() * (arr.size() - 1) / 2;
        
        for (int idx = 0; idx < arr.size(); ++idx) {
            Map.Entry<Integer, Integer> pair = arr.get(idx);
            for (int num : new int[]{pair.getKey(), pair.getValue()}) {
                indices.computeIfAbsent(num, k -> new ArrayList<>()).add(idx);
            }
        }

        int commonPairs = 0;
        for (Map.Entry<Integer, List<Integer>> entry : indices.entrySet()) {
            int size = entry.getValue().size();
            commonPairs += size * (size - 1) / 2;
        }
        
        return totalPairs - commonPairs;
    }

    public static void main(String[] args) {
        List<Map.Entry<Integer, Integer>> arr = new ArrayList<>();
        arr.add(new SimpleEntry<>(2, 5));
        arr.add(new SimpleEntry<>(1, 6));
        arr.add(new SimpleEntry<>(3, 2));
        arr.add(new SimpleEntry<>(4, 2));
        arr.add(new SimpleEntry<>(5, 1));
        arr.add(new SimpleEntry<>(6, 3));
        
        System.out.println("Count of non-common pairs: " + nonCommonPairs(arr));
    }
}