The “Aggressive Cows” problem is a classic binary search question that is often asked in coding interviews. <\/p>\n\n\n\n
It teaches you how to optimize placement problems using binary search. In this blog, we\u2019ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n You are given an array with unique elements of stalls[], <\/strong>which denote the position of a stall<\/strong>. You are also given an integer k<\/strong> which denotes the number of aggressive cows. Your task is to assign stalls <\/strong>to k <\/strong>cows such that the minimum distance <\/strong>between any two of them is the maximum <\/strong>possible.<\/p>\n\n\n\n Examples :<\/strong><\/p>\n\n\n\n Constraints:<\/strong> Let\u2019s solve the problem in the most straightforward way:<\/p>\n\n\n\n This approach is easy to understand but not efficient for large inputs.<\/p>\n\n\n\n
\n\n\n\nProblem Statement<\/strong><\/h2>\n\n\n\n
Input: <\/strong>stalls[] = [1, 2, 4, 8, 9], k = 3
Output: <\/strong>3
Explanation: <\/strong>The first cow can be placed at stalls[0],
the second cow can be placed at stalls[2] and
the third cow can be placed at stalls[3].
The minimum distance between cows, in this case, is 3, which also is the largest among all possible ways.<\/pre>\n\n\n\nInput: <\/strong>stalls[] = [10, 1, 2, 7, 5], k = 3\nOutput: <\/strong>4\nExplanation: <\/strong>The first cow can be placed at stalls[0],\nthe second cow can be placed at stalls[1] and\nthe third cow can be placed at stalls[4].\nThe minimum distance between cows, in this case, is 4, which also is the largest among all possible ways.<\/pre>\n\n\n\n
Input: <\/strong>stalls[] = [2, 12, 11, 3, 26, 7], k = 5\nOutput: <\/strong>1\nExplanation: <\/strong>Each cow can be placed in any of the stalls, as the no. of stalls are exactly equal to the number of cows.\nThe minimum distance between cows, in this case, is 1, which also is the largest among all possible ways.<\/pre>\n\n\n\n
2 <= stalls.size() <= 106<\/sup>
0 <= stalls[i] <= 108<\/sup>
2 <= k <= stalls.size()<\/p>\n\n\n
\n\n\n\nBrute Force Solution (Try Every Possible Distance)<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
Try every possible minimum distance from 1 up to the maximum possible (difference between the farthest and closest stall).<\/li>\n\n\n\n
For each distance, check if it is possible to place all cows with at least that much distance between them.<\/li>\n\n\n\n
The largest distance for which placement is possible is our answer.<\/li>\n\n\n\n
We check every possible distance, so we\u2019re sure to find the largest one that works.<\/li>\n<\/ol>\n\n\n\nCode Implementation<\/h3>\n\n\n\n