Binary TreesBinary Trees36
  1. 1Preorder Traversal of a Binary Tree using Recursion
  2. 2Preorder Traversal of a Binary Tree using Iteration
  3. 3Inorder Traversal of a Binary Tree using Recursion
  4. 4Inorder Traversal of a Binary Tree using Iteration
  5. 5Postorder Traversal of a Binary Tree Using Recursion
  6. 6Postorder Traversal of a Binary Tree using Iteration
  7. 7Level Order Traversal of a Binary Tree using Recursion
  8. 8Level Order Traversal of a Binary Tree using Iteration
  9. 9Reverse Level Order Traversal of a Binary Tree using Iteration
  10. 10Reverse Level Order Traversal of a Binary Tree using Recursion
  11. 11Find Height of a Binary Tree
  12. 12Find Diameter of a Binary Tree
  13. 13Find Mirror of a Binary Tree
  14. 14Left View of a Binary Tree
  15. 15Right View of a Binary Tree
  16. 16Top View of a Binary Tree
  17. 17Bottom View of a Binary Tree
  18. 18Zigzag Traversal of a Binary Tree
  19. 19Check if a Binary Tree is Balanced
  20. 20Diagonal Traversal of a Binary Tree
  21. 21Boundary Traversal of a Binary Tree
  22. 22Construct a Binary Tree from a String with Bracket Representation
  23. 23Convert a Binary Tree into a Doubly Linked List
  24. 24Convert a Binary Tree into a Sum Tree
  25. 25Find Minimum Swaps Required to Convert a Binary Tree into a BST
  26. 26Check if a Binary Tree is a Sum Tree
  27. 27Check if All Leaf Nodes are at the Same Level in a Binary Tree
  28. 28Lowest Common Ancestor (LCA) in a Binary Tree
  29. 29Solve the Tree Isomorphism Problem
  30. 30Check if a Binary Tree Contains Duplicate Subtrees of Size 2 or More
  31. 31Check if Two Binary Trees are Mirror Images
  32. 32Calculate the Sum of Nodes on the Longest Path from Root to Leaf in a Binary Tree
  33. 33Print All Paths in a Binary Tree with a Given Sum
  34. 34Find the Distance Between Two Nodes in a Binary Tree
  35. 35Find the kth Ancestor of a Node in a Binary Tree
  36. 36Find All Duplicate Subtrees in a Binary Tree
GraphsGraphs46
  1. 1Breadth-First Search in Graphs
  2. 2Depth-First Search in Graphs
  3. 3Number of Provinces in an Undirected Graph
  4. 4Connected Components in a Matrix
  5. 5Rotten Oranges Problem - BFS in Matrix
  6. 6Flood Fill Algorithm - Graph Based
  7. 7Detect Cycle in an Undirected Graph using DFS
  8. 8Detect Cycle in an Undirected Graph using BFS
  9. 9Distance of Nearest Cell Having 1 - Grid BFS
  10. 10Surrounded Regions in Matrix using Graph Traversal
  11. 11Number of Enclaves in Grid
  12. 12Word Ladder - Shortest Transformation using Graph
  13. 13Word Ladder II - All Shortest Transformation Sequences
  14. 14Number of Distinct Islands using DFS
  15. 15Check if a Graph is Bipartite using DFS
  16. 16Topological Sort Using DFS
  17. 17Topological Sort using Kahn's Algorithm
  18. 18Cycle Detection in Directed Graph using BFS
  19. 19Course Schedule - Task Ordering with Prerequisites
  20. 20Course Schedule 2 - Task Ordering Using Topological Sort
  21. 21Find Eventual Safe States in a Directed Graph
  22. 22Alien Dictionary Character Order
  23. 23Shortest Path in Undirected Graph with Unit Distance
  24. 24Shortest Path in DAG using Topological Sort
  25. 25Dijkstra's Algorithm Using Set - Shortest Path in Graph
  26. 26Dijkstra’s Algorithm Using Priority Queue
  27. 27Shortest Distance in a Binary Maze using BFS
  28. 28Path With Minimum Effort in Grid using Graphs
  29. 29Cheapest Flights Within K Stops - Graph Problem
  30. 30Number of Ways to Reach Destination in Shortest Time - Graph Problem
  31. 31Minimum Multiplications to Reach End - Graph BFS
  32. 32Bellman-Ford Algorithm for Shortest Paths
  33. 33Floyd Warshall Algorithm for All-Pairs Shortest Path
  34. 34Find the City With the Fewest Reachable Neighbours
  35. 35Minimum Spanning Tree in Graphs
  36. 36Prim's Algorithm for Minimum Spanning Tree
  37. 37Disjoint Set (Union-Find) with Union by Rank and Path Compression
  38. 38Kruskal's Algorithm - Minimum Spanning Tree
  39. 39Minimum Operations to Make Network Connected
  40. 40Most Stones Removed with Same Row or Column
  41. 41Accounts Merge Problem using Disjoint Set Union
  42. 42Number of Islands II - Online Queries using DSU
  43. 43Making a Large Island Using DSU
  44. 44Bridges in Graph using Tarjan's Algorithm
  45. 45Articulation Points in Graphs
  46. 46Strongly Connected Components using Kosaraju's Algorithm

Aggressive Cows Problem Optimal Binary Search Solution

Problem Statement

Given N stalls represented by their positions on a number line (sorted or unsorted), and K cows to place in these stalls, the goal is to place the cows such that the minimum distance between any two cows is as large as possible.

  • You must place exactly K cows in N stalls.
  • Each cow must be placed in a different stall.
  • The objective is to maximize the minimum distance between any two cows.

If the number of cows exceeds the number of stalls, it’s not possible to place all cows.

Examples

Stall Positions No. of Cows (K) Output Description
[1, 2, 4, 8, 9] 3 3 We can place cows at positions 1, 4, and 8 — min distance = 3
[1, 2, 4, 8, 9] 2 8 Place cows at positions 1 and 9 — max possible distance
[5, 17, 100, 111] 2 106 Place cows at 5 and 111 — max min distance is 106
[5, 17, 100, 111] 4 6 All cows must be placed, closest pair ends up at 6 units apart
[10] 1 0 Only one cow, no distance to maximize
[10] 2 -1 Not enough stalls to place 2 cows
[] 2 -1 Empty array, no stalls available
[2, 4, 6] 0 0 Zero cows, so minimum distance is trivially zero

Visualization Player

Solution

Understanding the Problem

We are given an array representing the positions of stalls along a straight line, such as [1, 2, 4, 8, 9]. Our goal is to place K cows in these stalls such that the **minimum distance between any two cows is as large as possible**.

In simpler words, the cows don't like being too close to each other. So, we have to spread them out in such a way that the closest pair of cows is still as far apart as we can manage — while still placing all cows.

This is a classic case of Binary Search on the Answer, where we don’t search through stall positions directly, but instead we ask: “What’s the largest minimum distance we can guarantee between any two cows?”

Step-by-Step Solution with Example

Step 1: Sort the Stall Positions

We begin by sorting the given array. This ensures that we consider stalls in proper order when placing cows.

Input: stalls = [1, 2, 8, 4, 9], cows = 3  
Sorted: [1, 2, 4, 8, 9]

Step 2: Apply Binary Search on Distance

We want to find the largest minimum distance possible. Let’s define our search space:

  • low = 1: The minimum possible distance (at least 1 unit apart)
  • high = max(stalls) - min(stalls) = 9 - 1 = 8: The maximum gap we could try

Step 3: Define the Feasibility Check

We write a helper function to check: "Is it possible to place all cows such that the minimum distance between them is at least mid?"

We try placing the first cow in the first stall, and then greedily place each next cow in the next stall that is at least mid away from the last one. If we can place all cows, return true, else false.

Step 4: Run Binary Search

We run a binary search loop:

  • Find the middle distance mid = Math.floor((low + high) / 2)
  • If placing cows with distance mid is possible → move to the right half to try a larger distance
  • If not possible → move to the left half to reduce distance

Keep track of the largest mid value for which placement worked — that will be our answer.

Step 5: Example Walkthrough

For stalls = [1, 2, 4, 8, 9] and K = 3, here's what the binary search would do:

Try mid = 4: Place cows at 1, 4, 8 → YES → try bigger
Try mid = 6: Place cows at 1, 9 → only 2 cows → NO → try smaller
Try mid = 5: Place cows at 1, 8 → only 2 cows → NO → try smaller
Try mid = 3: Place cows at 1, 4, 8 → YES → try bigger
Try mid = 4 (again): already checked

Eventually, we find that the largest minimum distance that allows all cows to be placed is 3.

Edge Cases

  • Only One Cow: If K = 1, we can place it anywhere. The answer is 0 since no second cow exists to compare distance.
  • Stalls Less Than Cows: If K > N, it's impossible to place all cows. We return -1 or throw an error.
  • All Stalls at Same Position: Example: [5, 5, 5]. No positive distance can be maintained → answer is 0.
  • Empty Stall List: No stall to place even a single cow → return -1.

Finally

This problem is a perfect example of how binary search can be used in non-obvious ways — not just on arrays, but also on possible “answers”.

It teaches us to focus on feasibility and gradually narrow down the range of possible solutions, ensuring both correctness and efficiency.

Time Complexity: O(N log(MaxDistance)), where N is the number of stalls.

It’s a powerful template for solving optimization problems involving placement, distance, and constraints.

Algorithm Steps

  1. Sort the arr in increasing order.
  2. Set low = 1 (smallest possible min distance) and high = arr[n - 1] - arr[0] (largest possible).
  3. Use binary search: while low ≤ high:
  4. → Compute mid = (low + high) / 2.
  5. → Check if it's possible to place k cows with at least mid distance between them.
  6. → If yes, store mid as a candidate and try for a larger value (low = mid + 1).
  7. → If not, reduce the distance (high = mid - 1).
  8. Return the largest valid mid found.

Code

Java
Python
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
import java.util.Arrays;

public class AggressiveCows {
    public static boolean canPlace(int[] stalls, int cows, int minDist) {
        int count = 1; // Place first cow at the first stall
        int lastPlaced = stalls[0];
        for (int i = 1; i < stalls.length; i++) {
            if (stalls[i] - lastPlaced >= minDist) {
                count++;
                lastPlaced = stalls[i];
                if (count == cows) return true;
            }
        }
        return false;
    }

    public static int solve(int n, int k, int[] arr) {
        Arrays.sort(arr);
        int low = 1, high = arr[n - 1] - arr[0];
        int result = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canPlace(arr, k, mid)) {
                result = mid; // Try for a bigger answer
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] stalls = {1, 2, 4, 8, 9};
        int k = 3;
        System.out.println("Max Min Distance: " + solve(stalls.length, k, stalls));
    }
}

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(n log(maxDist))Binary search on the distance (log(max position)) and each check takes O(n).
Average CaseO(n log(maxDist))Each iteration of binary search checks placement for given mid using O(n).
Worst CaseO(n log(maxDist))In the worst case, binary search runs log(max distance) steps and each step scans the stalls.

Space Complexity

O(1)

Explanation: No extra space apart from a few variables; we sort in-place and use constant memory.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.


Loading comments...