Company: Zomato
Difficulty: medium
Friends Problem Description Given N people. For a pair of people, they have a friend value A[i][j]. We want to split these people into N groups, such that each person belongs to exactly one group and each group contains at least one person. The partition value of a split is defined as the minimum friend value over all the pairs of different people within the same group. Find the maximum partition value possible. Suppose the minimum friend value of all pairs of different people from Group1 is min1 and from Group2 is min2. Then the partition value is defined as min(min1, min2). The first line of input contains an integer N representing the number of people. The next N lines contain N integers representing the friend value matrix A, where A[i][j] is the friend value between person i and person j. Examples Example 1: Input: 4 0 1 2 3 1 0 4 5 2 4 0 9 3 5 9 0 Output: 3 Example 2: Input: 4 0 702209411 496813081 673102149 702209411 0 561219907 738593611 496813081 561219907 0 814024114 67310214