leetcode Max Area of Island Solution (Max Area of Island) (leetcode june 2021 challenge)

Max Area of Island

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

 

Example 1:

 

Example 1:

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]

Output: 6

Explanation: The answer is not 11, because the island must be connected 4-directionally.

 

Example 2:

Input: grid = [[0,1,1,1,0,0,0,0]]

Output: 3

Constraints:

·         m == grid.length

·         n == grid[i].length

·         1 <= m, n <= 50

·         grid[i][j] is either 0 or 1.

 

Solution 1:

public class maxAreaOfIsland {

    public static int length(int[][] grid, int i, int j) {

        if (i >= grid.length || j >= grid[0].length || i < 0 || j < 0 || grid[i][j] != 1)

            return 0;

        int ans = 0;

        grid[i][j] = 2;

        if (j + 1 < grid[0].length && grid[i][j + 1] == 1)

            ans = ans + 1 + length(grid, i, j + 1);

        if (i + 1 < grid.length && grid[i + 1][j] == 1)

            ans = ans + 1 + length(grid, i + 1, j);

        if (j - 1 >= 0 && grid[i][j - 1] == 1)

            ans = ans + 1 + length(grid, i, j - 1);

        if (i - 1 >= 0 && grid[i - 1][j] == 1)

            ans = ans + 1 + length(grid, i - 1, j);

        return ans;

    }

    public static int Solution(int[][] grid) {

        int ans = 0;

        for (int i = 0; i < grid.length; i++) {

            for (int j = 0; j < grid[0].length; j++) {

                if (grid[i][j] == 1)

                    ans = Math.max(ans, length(grid, i, j) + 1);

            }

        }

        return ans;

    }

codeforces 45A Solution A. Codecraft lll (codeforces 45A) (rank 900*)

 45A. Codecraft lll

Problem Link: https://codeforces.com/problemset/problem/45/A

Solution 1:

import java.util.Scanner;

public class A45 {

    public static Scanner scn = new Scanner(System.in);

    public static String[] str = { "January", "February", "March", "April", "May", "June", "July", "August",

            "September", "October", "November", "December" };

    public static int nextIdx(int currIdx, int change) {

        return (currIdx + change) % 12;

    }

    public static int currIdx(String myStr) {

        for (int i = 0; i < str.length; i++) {

            if (myStr.equals(str[i]))

                return i;

        }

        return -1;

    }

    public static void main(String[] argv) {

        String str2 = scn.next();

        int change = scn.nextInt();

        int idx = currIdx(str2);

        System.out.println(str[nextIdx(idx, change)]);

    }

}

codeforces 282A Solution A. Bit++ (codeforces 282A) (rank 800*)

 282A. Bit++

Problem Link: https://codeforces.com/problemset/problem/282/A

Solution 1:

import java.util.*;

public class A282 {

    public static Scanner scn = new Scanner(System.in);

    public static int finalAns(int n){

        String str = "";

        int ans = 0;

        for(int i=0;i<n;i++){

            str=scn.next();

            if(str.charAt(0)=='+' || str.charAt(2)=='+') ans++;

            else ans--;

        }

        return ans;

    }

    public static void main(String[] argv){

        int n = scn.nextInt();

        System.out.println(finalAns(n));

    }

}

codeforces 263A Solution A. Beautiful Matrix (codeforces 263A) (rank 800*)

 263A. Beautiful Matrix

Problem Link: https://codeforces.com/problemset/problem/263/A

Solution 1:

import java.util.*;

public class A263 {

    public static Scanner scn = new Scanner(System.in);

    public static void input(int[][] arr) {

        for (int i = 0; i < 5; i++)

            for (int j = 0; j < 5; j++)

                arr[i][j] = scn.nextInt();

    }

    public static int TotalMoves(int[][] arr) {

        boolean flag = true;

        int x = 0, y = 0;

        for (int i = 0; i < 5; i++) {

            for (int j = 0; j < 5; j++) {

                if (arr[i][j] == 1) {

                    x = i;

                    y = j;

                    flag = false;

                    break;

                }

            }

            if (!flag)

                break;

        }

        return Math.abs(3-(x+1))+Math.abs(3-(y+1));

    }

    public static void main(String[] argv){

        int[][] arr = new int[5][5];

        input(arr);

        System.out.println(TotalMoves(arr));

    }

}

codeforces 43D Solution D.Journey (codeforces 43D) (rank 2000*)

43D. Journey

Problem Link: "https://codeforces.com/problemset/problem/43/D"

Solution 1:

import java.util.*;

public class traveseKing {

    public static Scanner scn = new Scanner(System.in);

 

    public static int counter = 0;

 

    public static boolean isTelepoter(int[][] arr, int i, int j, int n, int m, int count, ArrayList<int[]> al,

            int[][] dirEven, int[][] dirOdd) {

        if (n == 1 && m == 1) {

            System.out.println(0 + "\n" + 1 + "\t" + 1);

            return true;

        }

        if (count >= n * m - 1 && ((i == 1 && j == 2) || (i == 2 && j == 1))) {

            System.out.println(0 + "\n" + 1 + "\t" + 1);

            for (int x = 0; x < al.size(); x++) {

                for (int y = 0; y < 2; y++) {

                    System.out.print(al.get(x)[y] + "\t");

                }

                System.out.println();

            }

            System.out.println(1 + "\t" + 1);

 

            return true;

        }

 

        if (count >= n * m - 1)

            counter = count + 1;

        if (counter >= n * m)

            return false;

        boolean recAns = false;

 

        for (int x = 0; x < dirEven.length; x++) {

            int newi = 0, newj = 0;

            if (m % 2 == 0) {

                newi = i + dirEven[x][0];

                newj = j + dirEven[x][1];

            } else {

                newi = i + dirOdd[x][0];

                newj = j + dirOdd[x][1];

            }

            if ((newi <= n && newi >= 1) && (newj <= m && newj >= 1) && arr[newi - 1][newj - 1] < 1) {

                al.add(new int[] { newi,newj });

                arr[newi - 1][newj - 1]++;

                recAns = isTelepoter(arr, newi, newj, n, m, count + 1, al, dirEven, dirOdd);

                al.remove(al.size() - 1);

                arr[newi - 1][newj - 1]--;

            }

            if (recAns)

                return true;

        }

        return recAns;

 

    }

 

    public static void traverse(int[][] arr, int i, int j, int n, int m, ArrayList<int[]> al) {

        boolean isTele = true;

        int[][] dirOdd = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

        int[][] dirEven = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };

        isTele = isTelepoter(arr, 1, 1, n, m, 0, al, dirEven, dirOdd);

 

        if (!isTele) {

            System.out.println(1);

            if (n % 2 == 1)

                System.out.println(n + "\t" + m + "\t" + 1 + "\t" + 1);

            else

                System.out.println(n + "\t" + 1 + "\t" + 1 + "\t" + 1);

 

            for (int x = 0; x < n; x++) {

                if (x % 2 == 0)

                    for (int y = 0; y < m; y++) {

                        System.out.println((x + 1) + "\t" + (y + 1));

                    }

                else

                    for (int y = m - 1; y >= 0; y--) {

                        System.out.println((x + 1) + "\t" + (y + 1));

 

                    }

            }

            System.out.println(1 + "\t" + 1);

 

        }

 

    }

 

    public static void main(String[] argv) {

        int n = scn.nextInt();

        int m = scn.nextInt();

        ArrayList<int[]> al = new ArrayList<>();

        int[][] arr = new int[n][m];

        traverse(arr, 1, 1, n, m, al);

    }

}

Solution 2: Better than First:

import java.util.*;

public class traveseKing {

    public static Scanner scn = new Scanner(System.in);

    public static int counter = 0;

    public static boolean isTelepoter(int[][] arr, int i, int j, int n, int m, int count, ArrayList<int[]> al,

            int[][] dir) {

        if (n == 1 && m == 1) {

            System.out.println(0 + "\n" + 1 + "\t" + 1);

            return true;

        }

        if (count >= n * m - 1 && ((i == 1 && j == 2) || (i == 2 && j == 1))) {

            System.out.println(0 + "\n" + 1 + "\t" + 1);

            for (int x = 0; x < al.size(); x++) {

                for (int y = 0; y < 2; y++) {

                    System.out.print(al.get(x)[y] + "\t");

                }

                System.out.println();

            }

            System.out.println(1 + "\t" + 1);

            return true;

        }

        if (count >= n * m - 1)

            counter = count + 1;

        if (counter >= n * m)

            return false;

        boolean recAns = false;

        for (int x = 0; x < dir.length; x++) {

            int newi = 0, newj = 0;

            newi = i + dir[x][0];

            newj = j + dir[x][1];

            if ((newi <= n && newi >= 1) && (newj <= m && newj >= 1) && arr[newi - 1][newj - 1] < 1) {

                al.add(new int[] { newi, newj });

                arr[newi - 1][newj - 1]++;

                recAns = isTelepoter(arr, newi, newj, n, m, count + 1, al, dir);

                al.remove(al.size() - 1);

                arr[newi - 1][newj - 1]--;

            }

            if (recAns)

                return true;

        }

        return recAns;

    }

    public static void traverse(int[][] arr, int i, int j, int n, int m, ArrayList<int[]> al) {

        boolean istele= false;

        int[][] dirOdd = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

        int[][] dirEven = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };

         if (m % 2 == 1 && !(n % 2 == 1 && m % 2 == 1))

            istele = isTelepoter(arr, 1, 1, n, m, 0, al, dirOdd);

        if(m%2==0 && !(n % 2 == 1 && m % 2 == 1)) 

            istele = isTelepoter(arr, 1, 1, n, m, 0, al, dirEven);

        if (!istele) {

            System.out.println(1);

            if (n % 2 == 1)

                System.out.println(n + "\t" + m + "\t" + 1 + "\t" + 1);

            else

                System.out.println(n + "\t" + 1 + "\t" + 1 + "\t" + 1);

            for (int x = 0; x < n; x++) {

                if (x % 2 == 0)

                    for (int y = 0; y < m; y++) {

                        System.out.println((x + 1) + "\t" + (y + 1));

                    }

                else

                    for (int y = m - 1; y >= 0; y--) {

                        System.out.println((x + 1) + "\t" + (y + 1));

                    }

            }

            System.out.println(1 + "\t" + 1);

        } 

    }

    public static void main(String[] argv) {

        int n = scn.nextInt();

        int m = scn.nextInt();

        ArrayList<int[]> al = new ArrayList<>();

        int[][] arr = new int[n][m];

        traverse(arr, 1, 1, n, m, al);

    }

}

codeforces 158A Solution Next Round (codeforces 158A) (rank 800*)

158A. Next Round

Problem Link: https://codeforces.com/problemset/problem/158/A

Solution 1:

import java.util.*;

public class A158 {

    public static Scanner scn = new Scanner(System.in);

    public static int passedStudent(int[] arr, int value, int k) {

        int counter = 0;

        for (int i = 0; i < arr.length; i++) {

            if (value <= arr[i] && arr[i] > 0)

                counter++;

            else

                return counter;

        }

        return counter;

    }

    public static void input(int[] arr) {

        for (int i = 0; i < arr.length; i++)

            arr[i] = scn.nextInt();

    }

    public static void main(String[] argv) {

        int n = scn.nextInt();

        int k = scn.nextInt();

        int[] arr = new int[n];

        input(arr);

        if (arr[0] == 0)

            System.out.println(0);

        else

            System.out.println(passedStudent(arr, arr[k - 1], k));

    }

}