[Solution] Largest Square in the garden solution codechef

Largest Square in the garden solution codechef – Chef has a garden of size N×NN×N. The garden is divided into N2N2 squares of size 1×11×1 each.

Table of Contents

[Solution] Largest Square in the garden solution codechef

Chef has plants in some unit squares of the garden, because of which, that part looks green.
Formally, for the ithith row (0i<N)(0≤i<N), Chef has plants in all the columns from AiAi to BiBi (both inclusive) where 0AiBi<N0≤Ai≤Bi<N.

Help Chef find the length of the side of the largest square that is green.

Input Format

  • The first line contains an integer NN, the size of the garden.
  • The next NN lines contain two space-separated integers AiAi and BiBi, representing that plants are present in all the columns from AiAi to BiBi (both inclusive) of the ithith row.

Output Format

Output a single integer denoting the length of the side of the largest square that is green. In other words, output the length of the side of the square with maximum size, inside which all unit squares have plants.

[Solution] Largest Square in the garden solution codechef

  • 1N1061≤N≤106
  • 0AiBi<N0≤Ai≤Bi<N

Sample Input 1 

3
1 1
0 2
1 2

Sample Output 1 

2

Sample Input 2 

8
2 4
2 4
1 4
0 7
0 3
1 2
1 2
1 1

Sample Output 2 

3

[Solution] Largest Square in the garden solution codechef Explanation

Sample Explanation 11: The garden looks like:

The largest green square has vertices (1,1),(1,2),(2,2),(2,1)(1,1),(1,2),(2,2),(2,1). Thus, the length of the side of the largest green square is 22.

Sample Explanation 22: The garden looks like:

One of the largest green squares has vertices (0,2),(0,4),(2,4),(2,2)(0,2),(0,4),(2,4),(2,2). Thus, the length of the side of the largest green square is 33.
There may be other squares with same size but it can be proven that no square with length more than 33 is green.

For Solution

Click Here

Leave a Comment