Basket with Most Colors

Find the basket under a tree that receives the most different colors of flowers from its tree and adjacent trees.

Understand the Problem

Problem Statement

There are N trees in a straight line, each with flowers of different colors represented by uppercase letters (A-Z). Each tree has a basket under it numbered from 1 to N. Flowers fall directly into the basket under their tree and also into the baskets under adjacent trees. The task is to find the basket that contains the most different colors of flowers and print its number.

Note: If multiple baskets have the same maximum number of colors, print the first occurring basket number.

Constraints

2 ≤ N ≤ 1000
1 ≤ Length of each string ≤ 100
Each string contains only uppercase letters 'A' to 'Z'
All trees are in a straight line

Examples

Example 1

Input

3
R GG BG

Output

Explanation

Basket 1 gets colors from tree 1 (R) and tree 2 (G) = {R, G} (2 colors).
Basket 2 gets colors from tree 1 (R), tree 2 (G), and tree 3 (B) = {R, G, B} (3 colors).
Basket 3 gets colors from tree 2 (G) and tree 3 (B) = {G, B} (2 colors).
Basket 2 has the most colors, so output is 2.

Example 2

Input

5
RRGV G YYGG VIBGO GR

Output

Explanation

Basket 4 gets colors from tree 3 (Y, G), tree 4 (V, I, B, G, O), and tree 5 (G, R).
Combined unique colors: {Y, G, V, I, B, O, R} = 7 different colors.
No other basket has more than 7 colors.

Solution

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

#define MAX_N 1000
#define MAX_LEN 100

int main() {
    int N;
    scanf("%d", &N);
    
    char trees[MAX_N][MAX_LEN + 1];
    for (int i = 0; i < N; i++) {
        scanf("%s", trees[i]);
    }
    
    // Each basket can have at most 26 colors (A-Z)
    bool basket_colors[MAX_N][26] = {false};
    int count[MAX_N] = {0};
    
    // Process each tree
    for (int i = 0; i < N; i++) {
        // Add colors to current basket (i)
        for (int j = 0; j < strlen(trees[i]); j++) {
            char color = trees[i][j];
            if (!basket_colors[i][color - 'A']) {
                basket_colors[i][color - 'A'] = true;
                count[i]++;
            }
        }
        
        // Add colors to left adjacent basket (i-1) if exists
        if (i > 0) {
            for (int j = 0; j < strlen(trees[i]); j++) {
                char color = trees[i][j];
                if (!basket_colors[i-1][color - 'A']) {
                    basket_colors[i-1][color - 'A'] = true;
                    count[i-1]++;
                }
            }
        }
        
        // Add colors to right adjacent basket (i+1) if exists
        if (i < N - 1) {
            for (int j = 0; j < strlen(trees[i]); j++) {
                char color = trees[i][j];
                if (!basket_colors[i+1][color - 'A']) {
                    basket_colors[i+1][color - 'A'] = true;
                    count[i+1]++;
                }
            }
        }
    }
    
    // Find basket with maximum colors
    int max_colors = 0;
    int best_basket = 1;
    
    for (int i = 0; i < N; i++) {
        if (count[i] > max_colors) {
            max_colors = count[i];
            best_basket = i + 1; // Convert to 1-based indexing
        }
    }
    
    printf("%d\n", best_basket);
    return 0;
}

Time:O(N * M) where N is number of trees and M is the maximum length of any tree's color string. Each color is processed at most 3 times (for 3 baskets), which is still O(N*M).

Space:O(N) for the count array and boolean tracking arrays. The input storage is O(N*M). The 2D boolean array is O(N*26) = O(N).

Approach:

C Solution Explanation:

Data Structures: Use a 2D boolean array basket_colors[N][26] to track which colors each basket has, and an integer array count[N] to store the number of unique colors per basket.
Processing: For each tree i, iterate through its color string and add each color to baskets i-1, i, and i+1 (if they exist), ensuring no duplicates within a basket using the boolean tracker.
Result: After processing all trees, scan the count array to find the basket with the maximum unique colors, returning the first occurrence in case of ties.

Key Points: Uses boolean arrays for O(1) color lookup, handles boundary conditions (first and last trees), converts between 0-based array indexing and 1-based basket numbering.

Visual Explanation

Loading diagram...

All Problems