Tuesday, September 17, 2024

 


Given an array of varying heights above sea level for adjacent plots, and the array of water levels on consecutive days, find the number of islands. An island is a slice of array such that plots adjacent to the boundary of the island are under water.

class Solution { 

public int[] solution(int[] A, int[] B) {

    return Arrays

    .stream(B)

    .map(water -> IntStream

         .range(0, N)

         .filter(j -> (A[j] > water) && (j == N - 1 || A[j + 1] <= water))

         .map(i -> 1)

         .sum()) .toArray();

}

}

For example, given the following arrays A and B:

    A[0] = 2    B[0] = 0

    A[1] = 1    B[1] = 1

    A[2] = 3    B[2] = 2

    A[3] = 2    B[3] = 3

    A[4] = 3    B[4] = 1

Solution: 

result[0] = 1

result[1] = 2

result[2] = 2

result[3] = 0

result[4] = 2


For a water level, the number of islands is just the sum of changes in the number of islands as the water level is decreasing.

Optimized solution:

class Solution { 

public int[] solution(int[] A, int[] B) {

     int limit = Math.max(maxLevel(A), maxLevel(B));

     int[] island = new int[limit + 2];

     IntStream.range(0, A.length - 1)

                       .filter( j -> A[j]  > A[j+1])

                      .forEach(j ->  {

                                       island[A[j]] += 1;

                                       island[A[j + 1]] -= 1;

                       });

     island[A[A.length-1]] += 1;

     IntStream.range(-limit, 0)

                      .forEach(i -> island[-i] += island[-i+1]);

     return Arrays.stream(B).map(water -> island[water + 1]).toArray();

}

public int maxLevel(int[] A) {

       return Arrays.stream(A).max().getAsInt();

}

}


// before cumulation

island[0] = 0

island[1] = -1

island[2] = 0

island[3] = 2

island[4] = 0

// after cumulation

island[0] = 1

island[1] = 1

island[2] = 2

island[3] = 2

island[4] = 0


result[0] = 1

result[1] = 2

result[2] = 2

result[3] = 0

result[4] = 2



No comments:

Post a Comment