[Algorithm] Exhaustive Search - Business Card Wallet sample case

Problem Description

Business Card Wallet

 

A company that manufactures business card wallets is trying to determine the size of their wallet. The wallet must be able to hold business cards of various shapes and sizes, while still being small and convenient to carry.

To design a wallet that satisfies these requirements, the design team surveyed the width and height of all business cards.

The table below shows the width and height of 4 business cards:

Card No.	Width	Length
1	60	50
2	30	70
3	60	30
4	80	40

 

Since the longest width and height are 80 and 70 respectively, a wallet of size 80 (W) × 70 (H) can hold all business cards. However, if card #2 is rotated horizontally, all cards can be accommodated in a wallet of size 80 (W) × 50 (H). The size of this wallet is 4000 (= 80 × 50).

---

Task

You are given a 2D array sizes as a parameter, where each element represents the width and height of a business card. Complete the solution function to return the minimum wallet size that can hold all business cards.

---

Constraints

• The length of sizes is between 1 and 10,000.
• Each element of sizes is in the format [w, h].
  • w represents the width of the business card.
  • h represents the height of the business card.
  • Both w and h are natural numbers between 1 and 1,000.

My Approach

Goal: Find the minimum wallet size that can hold all business cards.

Strategy: For each card, identify which dimension is longer and which is shorter. Track the largest value seen among the "longer" dimensions, and separately track the largest value seen among the "shorter" dimensions across all cards. The wallet's width is determined by the largest of the longer dimensions, and the wallet's height by the largest of the shorter dimensions.

Rationale: Every card can be rotated, so we can always orient it such that the longer side aligns with the wallet's width and the shorter side aligns with the wallet's height. By consistently categorizing each card's dimensions this way and finding the maximum in each category independently, we arrive at the tightest possible wallet that can accommodate all cards in their optimal orientation.

My Solution (Key Idea: Normalize first, then compare )

class Solution {
    public int solution(int[][] sizes) {
        int answer = 0;
        int longestWidth = Math.max(sizes[0][0], sizes[0][1]);
        int longestLength = Math.min(sizes[0][0], sizes[0][1]);
        int nowWidth;
        int nowLength;
        for(int i = 0; i < sizes.length; i++) {
            nowWidth = Math.max(sizes[i][0], sizes[i][1]);
            nowLength = Math.min(sizes[i][0], sizes[i][1]);
            if(longestWidth < nowWidth) {
                longestWidth = nowWidth;
            }
            if(longestLength < nowLength) {
                longestLength = nowLength;
            }
        }
        return longestWidth * longestLength;
    }
}

 

Strengths:

 

• Correct: Logic is sound and produces the right result.
• Explicit and easy to trace: The step-by-step structure makes it approachable for beginners to understand.

 

Limitations (or Trade-offs):

 

• Redundant initialization: sizes[0] is manually used to seed the initial values, then the loop iterates from index 0 again — processing the first card twice unnecessarily. Either initialize to 0 (as Candidate #2 does) or start the loop from index 1.
• int answer = 0 is declared but never used — dead code, which signals a lack of attention to detail during cleanup.
• Index-based for-loop is unnecessarily verbose here; an enhanced for-loop would be cleaner.
• Manual if comparisons instead of Math.max() makes the code more verbose than needed.
• Naming: nowWidth / nowLength feel informal; currentWidth / currentHeight would be more professional.

 

---

Best Practice (Key Idea:  Track two independent maximums in one pass )

class Solution {
    public int solution(int[][] sizes) {
        int length = 0, height = 0;
        for (int[] card : sizes) {
            length = Math.max(length, Math.max(card[0], card[1]));
            height = Math.max(height, Math.min(card[0], card[1]));
        }
        int answer = length * height;
        return answer;
    }
}

 

Strengths:

 

• Correct and clean: The core logic — normalizing each card so the larger dimension is always treated as length — is sound and produces the right answer.
• Readable: Variable names and structure are easy to follow.
• Efficient: Single pass O(n) with O(1) space, no unnecessary allocations.
• Enhanced for-loop is idiomatic and preferred over index-based iteration when the index isn't needed.

 

Limitations (or Trade-offs):

 

• Minor: int answer = length * height; return answer; can simply be return length * height; — the intermediate variable adds no value here.
• Variable name length could be more descriptive (e.g., maxLong, maxWidth) to better reflect domain intent, since length and height are semantically close and can cause confusion.

 

 

---

Alternative Approaches (Key Idea: Fold everything into one reduction)

import java.util.*;
class Solution {
    public int solution(int[][] sizes) {
        return Arrays.stream(sizes).reduce((a, b) -> new int[]{
                Math.max(Math.max(a[0], a[1]), Math.max(b[0], b[1])), Math.max(Math.min(a[0], a[1]), Math.min(b[0], b[1]))
        }).map(it -> it[0] * it[1]).get();
    }
}

 

Strengths: Demonstrates familiarity with Java Streams and functional-style programming.

Limitations (or Trade-offs):

 

• Correctness concern: Using reduce() this way is problematic. The accumulator treats the first element a as an already-reduced result, but in the first iteration a is a raw card [w, h], not a normalized [max, min] pair. This can produce incorrect results depending on the input order.
• Readability: The one-liner is extremely dense and difficult to parse at a glance. Readability and maintainability should be prioritized over brevity.
• Unnecessary object allocation: A new int[] is created on every reduction step, adding unnecessary heap pressure for large inputs.
• Optional.get() without check: Calling .get() on an Optional without isPresent() guard will throw NoSuchElementException on an empty input, which is poor defensive programming.

 

Lessons Learned

 

Dead code signals lack of attention to details.
Index-based for loop is verbose when enhanced for-loop is applicable
Try using more formal expressions (now -> current)

 

My Github Repository for Solution Code

[level 1] Title: 최소직사각형, Time: 1.65 ms, Memory: 99.2 MB -BaekjoonHub · ginsengcandy/Coding-Test-Practice@76e052e

 

Problem Source

프로그래머스