Scribd Logo
Upload

Welcome to Scribd!

  • 22 views

    14-03-2023

    Uploaded by

    Kamma Vidya
    Here are the key steps to solve this problem: 1. Create a horizontal histogram for each row which stores the maximum width for each column. 2. Iterate through each cell of the matrix from top to bottom. 3. For each cell, calculate the area of rectangle using the histogram value of current row and previous rows. 4. Update the maximum area. 5. Return the maximum area. The time complexity is O(n*m) as we iterate each cell once. Auxiliary space is O(m) to store histogram for each row.

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd

    14-03-2023

    Uploaded by

    Kamma Vidya
    22 views4 pages
    Here are the key steps to solve this problem: 1. Create a horizontal histogram for each row which stores the maximum width for each column. 2. Iterate through each cell of the matrix from top to bottom. 3. For each cell, calculate the area of rectangle using the histogram value of current row and previous rows. 4. Update the maximum area. 5. Return the maximum area. The time complexity is O(n*m) as we iterate each cell once. Auxiliary space is O(m) to store histogram for each row.

    Copyright

    © © All Rights Reserved

    Available Formats

    TXT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Here are the key steps to solve this problem: 1. Create a horizontal histogram for each row which stores the maximum width for each column. 2. Iterate through each cell of the matrix from top to bottom. 3. For each cell, calculate the area of rectangle using the histogram value of current row and previous rows. 4. Update the maximum area. 5. Return the maximum area. The time complexity is O(n*m) as we iterate each cell once. Auxiliary space is O(m) to store histogram for each row.

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd
    Download as txt, pdf, or txt
    22 views4 pages

    14-03-2023

    Uploaded by

    Kamma Vidya
    Here are the key steps to solve this problem: 1. Create a horizontal histogram for each row which stores the maximum width for each column. 2. Iterate through each cell of the matrix from top to bottom. 3. For each cell, calculate the area of rectangle using the histogram value of current row and previous rows. 4. Update the maximum area. 5. Return the maximum area. The time complexity is O(n*m) as we iterate each cell once. Auxiliary space is O(m) to store histogram for each row.

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd
    Download as txt, pdf, or txt
    You are on page 1of 4

    /*

    write a program to read an array of elements & rotate array of k elements from
    the array
    for other boundary conditions print -1.

    for example:
    input:
    5
    3
    1 2 3 4 5

    Output:
    3 4 5 1 2

    first line reads the size of the array, followed by k elements to rotate ,then
    followed by elements
    so given elements 1 2 3 4 5 we need to rotate three times
    elements in first rotation 5 1 2 3 4
    elements in second rotation 4 5 1 2 3
    elements in third rotation 3 4 5 1 2 .
    so output will be 3 4 5 1 2

    */

    case=1
    input=5
    5
    1 2 3 4 5
    output=1 2 3 4 5

    case=2
    input=5
    6
    1 2 3 4 5
    output=5 1 2 3 4

    case=3
    input=5
    -2
    1 2 3 4 5
    output=-1

    import java.util.*;

    public class RotateArray {

    /* write your code here */


    public static void rotateArray(int[] arr, int k) {
    for (int i = 0; i < k; i++) {
    for (int j = arr.length - 1; j > 0; j--) {
    int temp = arr[j];
    arr[j] = arr[j - 1];
    arr[j - 1] = temp;
    }
    }
    }
    /* utility function to print an array */
    void printArray(int arr[], int n)
    {
    for (int i = 0; i < n; i++)
    System.out.print(arr[i] + " ");
    }

    public static void main(String[] args)


    {
    RotateArray rotate = new RotateArray();
    Scanner sc = new Scanner(System.in);
    int arraySize = sc.nextInt();
    int k = sc.nextInt();
    int[] arr = new int[arraySize];
    for(int i=0;i<arraySize;i++)
    arr[i] = sc.nextInt();

    if (arr == null || k < 0) {


    System.out.print("-1");
    }else{
    rotate.rotateArray(arr, k);
    rotate.printArray(arr, arraySize);
    }

    /*
    *
    You have a list of words and a pattern, and you want to know which words in words
    matches the pattern.

    A word matches the pattern if there exists a permutation of letters p so that after
    replacing
    every letter x in the pattern with p(x), we get the desired word.

    (Recall that a permutation of letters is a bijection from letters to letters:


    every letter maps to another letter, and no two letters map to the same letter.)

    Return a list of the words in words that match the given pattern.

    print the answer in ascending order.

    Note:
    1 <= words.length <= 50
    1 <= pattern.length = words[i].length <= 20

    Sample Input:
    abc deq mee aqq dkd ccc
    abb

    Sample Output:
    aqq mee

    Explanation:
    "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}.
    "ccc" does not match the pattern because {a -> c, b -> c, ...} is not a
    permutation,
    since a and b map to the same letter.
    *
    */

    case=1
    input=pqrs psps lmno lmlm
    abab
    output=lmlm psps

    case=2
    input=bpqrs ppsps almno lmlm nnono cckck
    jjljl
    output=cckck nnono ppsps

    case=3
    input=ssske wxyz abcd iikl jklm
    zyxw
    output=abcd jklm wxyz

    case=4
    input=ssske wxyz abcd iikl jklm klmnn opqrs
    zyxww
    output=klmnn

    import java.util.*;

    public class FindAndReplacePattern {

    public static List<String> findAndReplacePattern(String[] words, String


    pattern) {
    List<String> ans = new ArrayList();
    for (String word : words){
    if (word.length()==pattern.length())
    if (match(word, pattern))
    ans.add(word);
    }
    return ans;
    }

    public static boolean match(String word, String pattern) {


    Map<Character, Character> m1 = new HashMap();
    Map<Character, Character> m2 = new HashMap();

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


    char w = word.charAt(i);
    char p = pattern.charAt(i);
    if (!m1.containsKey(w))
    m1.put(w, p);
    if (!m2.containsKey(p))
    m2.put(p, w);
    if (m1.get(w) != p || m2.get(p) != w)
    return false;
    }

    return true;
    }

    public static void main(String[] args) {


    Scanner sc = new Scanner(System.in);
    String wordsString = sc.nextLine();
    String words[]= wordsString.split(" ");
    String pattern= sc.next();
    List<String> ans = new ArrayList();
    ans = findAndReplacePattern(words,pattern);
    Collections.sort(ans);
    ans.stream().forEach(s -> System.out.print(s+" "));

    }
    }

    Given a binary matrix M of size n X m. Find the maximum area of a rectangle formed
    only of 1s in the given matrix.

    Example 1:

    Input:
    n = 4, m = 4
    M[][] = {{0 1 1 0},
    {1 1 1 1},
    {1 1 1 1},
    {1 1 0 0}}
    Output: 8
    Explanation: For the above test case the
    matrix will look like
    0 1 1 0
    1 1 1 1
    1 1 1 1
    1 1 0 0
    the max size rectangle is
    1 1 1 1
    1 1 1 1
    and area is 4 *2 = 8.
    Your Task:
    Your task is to complete the function maxArea which returns the maximum size
    rectangle area in a binary-sub-matrix with all 1’s. The function takes 3 arguments
    the first argument is the Matrix M[ ] [ ] and the next two are two integers n and m
    which denotes the size of the matrix M.

    Expected Time Complexity : O(n*m)


    Expected Auixiliary Space : O(m)

    You might also like