Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • EspaΓ±ol

β€ΊProblems: Arrays & Strings

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

Rotate Matrix

Given a 2 dimensional array that looks like an NxN matrix, where each slot has a integer, write a method to rotate the matrix to the right. (can you do this in place?)

int[][] exampleMatrix = {
    {1,2,3},
    {4,5,6},
    {7,8,9},
};
// all the items have been rotated from left to right
int[][] exampleResponse = {
    {7,4,1},
    {8,2,6},
    {9,6,3}
};

πŸ‘‰ Link here to the repo to solve the problem

imagen

πŸ‘Œ Tips

Try thinking about it layer by layer. Can you rotate a specific layer?

Rotating a specific layer would just mean swapping the values in four arrays. If you were asked to swap the values in two arrays, could you do this? Can you then extend it to four arrays?

πŸ‘Š Solution 1

I've implemented a simple solution which uses another matrix as a placeholder in order to append the numbers over which im iterating through the matrix. This solution will take O(N^2).

int[][] solution(int[][] matrix) {
        int[][] result = {
                {0,0,0},
                {0,0,0},
                {0,0,0}
        };

        for (int i = 0; i < matrix.length; i++) {
            int c = 0;
            for (int j = matrix.length - 1; j >= 0; j--) {
                int current = matrix[i][j];
                result[c][i] = current;
                c++;
            }
            c = 0;
        }
        return result;
    }

This solution is also taking O(N^2) space, could you find a way of reducing the space to O(1) by doing the replacement in place?


Question added by Diego Romero

Last updated on 3/4/2020
← String CompressionZero Matrix β†’
  • πŸ‘‰ Link here to the repo to solve the problem
  • πŸ‘Œ Tips
  • πŸ‘Š Solution 1
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright Β© 2021 Kodr