Properties Graph - Practice Coding Problems

Properties Graph - Problem

Array Hash Table Depth-First Search Breadth-First Search Union Find Graph Medium

You are given a 2D integer array properties having dimensions n x m and an integer k.

Define a function intersect(a, b) that returns the number of distinct integers common to both arrays a and b.

Construct an undirected graph where each index i corresponds to properties[i]. There is an edge between node i and node j if and only if intersect(properties[i], properties[j]) >= k, where i and j are in the range [0, n - 1] and i != j.

Return the number of connected components in the resulting graph.

Input & Output

Example 1 — Basic Graph Formation

$ Input: properties = [[1,2,3],[1,3],[2,3,4]], k = 2

› Output: 2

💡 Note: Intersections: properties[0] ∩ properties[1] = {1,3} (size 2 ≥ k), properties[0] ∩ properties[2] = {2,3} (size 2 ≥ k), properties[1] ∩ properties[2] = {3} (size 1 < k). Edges: 0-1, 0-2. Components: {0,1,2} and {} → But node 2 connects to 0, so actually {0,1,2} is one component. Wait, let me recalculate: 0 connects to 1 and 2, so all three are connected → 1 component.

Example 2 — No Connections

$ Input: properties = [[1,2],[3,4],[5,6]], k = 2

› Output: 3

💡 Note: No two arrays have 2 or more common elements, so no edges exist. Each node forms its own component: 3 components total.

Example 3 — All Connected

$ Input: properties = [[1,2,3,4],[1,2,5,6],[2,3,7,8]], k = 2

› Output: 1

💡 Note: All pairs have at least 2 common elements: (0,1) share {1,2}, (0,2) share {2,3}, (1,2) share {2}. Wait, (1,2) only share {2}, which is size 1 < k=2. So edges are 0-1 and 0-2, making one component {0,1,2}.

Constraints

1 ≤ properties.length ≤ 10³
1 ≤ properties[i].length ≤ 10³
1 ≤ properties[i][j] ≤ 10⁵
1 ≤ k ≤ 10³

Visualization

Tap to expand

Understanding the Visualization

Input Properties

Each array becomes a node in the graph

Find Intersections

Connect nodes with intersection size ≥ k

Count Components

Find connected components in the resulting graph

Key Takeaway

🎯 Key Insight: Transform array similarity into graph connectivity - nodes with enough common elements form connected components

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Facebook 18

The key insight is to model this as a graph connectivity problem where nodes are property arrays and edges exist when intersection size ≥ k. Best approach uses hash sets for O(1) intersection counting and Union-Find for efficient component tracking. Time: O(n²×m), Space: O(n×m)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with DFS	O(n² × m)	O(n + E)	Compare all pairs, build adjacency list, then count connected components with DFS
Optimized with Hash Sets	O(n² × m + n × m)	O(n × m)	Use hash sets for O(1) intersection counting, reducing time complexity significantly

Brute Force with DFS — Algorithm Steps

Compare all pairs O(n²) to count intersections
Build adjacency list for valid edges
Use DFS to find connected components

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Pairs

Count common elements between all pairs of property arrays

Build Graph

Create edges for pairs with intersection >= k

Count Components

Use DFS to find connected components

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

void dfs(int** graph, int* graph_sizes, bool* visited, int node) {
    visited[node] = true;
    for (int i = 0; i < graph_sizes[node]; i++) {
        int neighbor = graph[node][i];
        if (!visited[neighbor]) {
            dfs(graph, graph_sizes, visited, neighbor);
        }
    }
}

int solution(int** properties, int* propertySizes, int propertiesSize, int k) {
    int n = propertiesSize;
    if (n == 0) return 0;
    
    // Build adjacency list
    int** graph = (int**)malloc(n * sizeof(int*));
    int* graph_sizes = (int*)calloc(n, sizeof(int));
    int* graph_capacity = (int*)malloc(n * sizeof(int));
    
    for (int i = 0; i < n; i++) {
        graph[i] = (int*)malloc(10 * sizeof(int));
        graph_capacity[i] = 10;
    }
    
    // Compare all pairs to find edges
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // Count intersection
            int intersection = 0;
            for (int x = 0; x < propertySizes[i]; x++) {
                for (int y = 0; y < propertySizes[j]; y++) {
                    if (properties[i][x] == properties[j][y]) {
                        intersection++;
                        break;
                    }
                }
            }
            
            if (intersection >= k) {
                // Add edge i-j
                if (graph_sizes[i] >= graph_capacity[i]) {
                    graph_capacity[i] *= 2;
                    graph[i] = (int*)realloc(graph[i], graph_capacity[i] * sizeof(int));
                }
                graph[i][graph_sizes[i]++] = j;
                
                // Add edge j-i
                if (graph_sizes[j] >= graph_capacity[j]) {
                    graph_capacity[j] *= 2;
                    graph[j] = (int*)realloc(graph[j], graph_capacity[j] * sizeof(int));
                }
                graph[j][graph_sizes[j]++] = i;
            }
        }
    }
    
    // Count connected components using DFS
    bool* visited = (bool*)calloc(n, sizeof(bool));
    int components = 0;
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(graph, graph_sizes, visited, i);
            components++;
        }
    }
    
    // Cleanup
    for (int i = 0; i < n; i++) {
        free(graph[i]);
    }
    free(graph);
    free(graph_sizes);
    free(graph_capacity);
    free(visited);
    
    return components;
}

int main() {
    // Simple parsing - assume small input for demo
    int n = 3; // Example size
    int k = 2;
    
    // Example: [[1,2,3],[1,3],[2,3,4]]
    int** properties = (int**)malloc(n * sizeof(int*));
    int* propertySizes = (int*)malloc(n * sizeof(int));
    
    // Hardcoded example
    properties[0] = (int*)malloc(3 * sizeof(int));
    properties[0][0] = 1; properties[0][1] = 2; properties[0][2] = 3;
    propertySizes[0] = 3;
    
    properties[1] = (int*)malloc(2 * sizeof(int));
    properties[1][0] = 1; properties[1][1] = 3;
    propertySizes[1] = 2;
    
    properties[2] = (int*)malloc(3 * sizeof(int));
    properties[2][0] = 2; properties[2][1] = 3; properties[2][2] = 4;
    propertySizes[2] = 3;
    
    int result = solution(properties, propertySizes, n, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × m)

Compare all n² pairs, each intersection takes O(m) time

⚠ Quadratic Growth

Space Complexity

O(n + E)

Adjacency list storage plus DFS recursion stack

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~25 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler