Home Blog Page 12

Solving Leetcode 94. Binary Tree Inorder Traversal

0

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

The inorder traversal of a binary tree is the nodes in the tree listed in the order they would be visited by an inorder traversal. To solve this problem, we can use a stack to keep track of the nodes we have visited. We will push the root node onto the stack and then pop it off when we are done visiting its left subtree. We will then visit the right subtree of the root.

In this blog post, we will solve leetcode question 94 – Binary Tree Inorder Traversal. This is a classic computer science problem that can be solved using a number of different algorithms. We will discuss two different solutions – a recursive solution and an iterative solution. Let’s get started!

Simplifying the problem

Leetcode 94 question asks us to traverse a binary tree in order. In order to make this easier, let’s simplify the problem by thinking about it as traversing a linked list instead of a binary tree. We can think of each node in the tree as having two pointers – one pointing to the left child and one pointing to the right child.

Lusera leetcode 94 traversal with stack
Input: root = [1,null,2,3]

We are placingall the left nodes of the current node into stack. node is now null since we keep assigning node to its left node after placing the current node into stack.

Solutions

Recursive Solution

The recursive solution for leetcode 94 is a straightforward one. We can use a simple recursive function to traverse the binary tree in order from left to right. We start by visiting the left-most node and then recursively call our function on each of its children (the left and right nodes). This will cause our function to traverse the tree in order from left to right.

Iterative Solution

The iterative solution for leetcode 94 is slightly more complex, but still manageable. We can use a stack to store our current node and its children (the left and right nodes). We start by pushing the root node of the binary tree onto the stack and then while the stack is not empty, we pop a node off of it. We then process it by printing its value and pushing its left and right nodes (if they are not null) onto the stack. Then, when there are no more nodes on the stack, our inorder traversal will be complete.

Solution one is using a stack. Here is the code in JavaScript

var inorderTraversal = function(root) {
    var stack = [];
    var result = [];
    
    // while there is a root or there are still nodes in the stack
    while(root || stack.length){
        // while there is a root
        // push the root into the stack
        // and set the root to the root's left child
        while(root){
            stack.push(root);
            root = root.left;
        }
        // set the root to the node at the top of the stack
        root = stack.pop();
        // push the root's value into the result array
        result.push(root.val);
        // set the root to the root's right child
        root = root.right;
    }
    
    return result;
};

Code in Python

def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result, stack = [], [(root, False)]
        while stack:
            root, is_visited = stack.pop()
            if root is None:
                continue
            if is_visited:
                result.append(root.val)
            else:
                stack.append((root.right, False))
                stack.append((root, True))
                stack.append((root.left, False))
        return result

Code in Java

   public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            result.add(root.val);
            root = root.right;
        }
        
        return result;
    }

The time complexity is O(n) and the space complexity is O(n).

Solving Leetcode 102. Binary Tree Level Order Traversal

0

From Leetcode:

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]

What is being asked?

The questions seems to be pretty straight forward. Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level). For example: Given binary tree [3,9,20,null,null,15,7],

/*
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

*/

return its level order traversal as: [ [3], [9,20], [15,7] ]

What are ways to solve it?

There are multiple ways to solve this problem. One way would be to use a queue. We would start by putting the root node into the queue. Then, we would loop through the queue until it is empty. For each node in the queue, we would add its left and right child nodes (if they exist) to the queue. We would also add the value of the node to our result array.

What is the most optimal Way?

The most optimal way to solve this problem would be to use a breadth-first search algorithm.
The time complexity of this algorithm is O(n), where n is the number of nodes in the tree. The space complexity is also O(n), since we need to store the nodes in the queue as well as the values in the result array. Let’s code this one.

var levelOrder = function(root) {
  // create a queue and result array
  let queue = [root];
  let result = [];
  
  // if the root is null, return an empty array
  if (!root) return result;
  
  // loop through the queue until it is empty
  while (queue.length > 0) {
    // store the size of the queue
    let size = queue.length;
    
    // create an array to store the values for this level
    let level = [];
    
    // loop through the queue
    for (let i = 0; i < size; i++) {
      // dequeue a node
      let node = queue.shift();
      
      // add the value of the node to the level array
      level.push(node.val);
      
      // if the node has a left child, add it to the queue
      if (node.left) queue.push(node.left);
      
      // if the node has a right child, add it to the queue
      if (node.right) queue.push(node.right);
    }
    
    // add the level array to the result array
    result.push(level);
  }
  
  // return the result array
  return result;
};

Implementing a Binary Tree

0

If I had to pick the single most important topic in software development, it would be data structures. One of the most common and easiest ones is a tree — a hierarchical data structure. In this article, let’s explore Trees in Java.

  • What is a Binary Tree?
  • Types of Binary Tree
  • Binary Tree Implementation
  • Tree Traversals
  • Applications of Binary Tree

What is a Binary Tree?

A binary tree is a data structure that allows two nodes to be linked together by a path from the root to the leftmost child, and from the leftmost child to the rightmost child. The path is called a path from the root to the leftmost child, and from the leftmost child to the rightmost child.

A binary tree has the following properties:

  • Each node has at most two children
  • The left child of a node is less than the right child of a node
  • The right child of a node is greater than the left child of a node
  • A node is a leaf node if it has no children

Examples of coding problems using trees:

What is the difference between a binary tree and a binary search tree?

A binary tree is a data structure that allows two nodes to be linked together by a path from the root to the leftmost child, and from the leftmost child to the rightmost child. The path is called a path from the root to the leftmost child, and from the leftmost child to the rightmost child.

A binary search tree is a data structure that allows two nodes to be linked together by a path from the root to the leftmost child, and from the leftmost child to the rightmost child, such that the left child is less than the right child.

Each data element stored in a tree structure called a node. A Tree node contains the following parts:
1. Data

2. Pointer to left child

3. Pointer to the right child

  • Binary search trees support many dynamic-set operations, including SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT and DELETE.
  • Basic operations on a binary search tree take time proportional to the height of the tree – which is O(lg n) for a complete binary tree with n nodes.
  • In practice, we can’t always guarantee that binary search trees are built randomly – but there are variations (like red-black trees) with good guaranteed worst-case performance on basic operations.
  • After presenting the basic properties of binary search trees, the following sections show how to walk a binary search tree to print its values in sorted order; how to find a value in a binary search; minimum or maximum element; predecessor or successor of an element; insert into or delete from a binary search tree.

We can represent a tree node using class. Below is an example of a tree node with integer data.

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
class Node {
 
    int value;
    Node left;
    Node right;
 
    Node(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

What are the Types of Binary Trees?

The three types of binary trees are full, complete, and perfect.

A full binary tree is a binary tree in which every node has either zero or two children. A full binary tree is also sometimes called a proper or strict binary tree.

A complete binary tree is a binary tree in which every level of the tree is fully filled, except for possibly the last level. The last level of a complete binary tree is filled from left to right. explain a perfect binary tree A perfect binary tree is a binary tree in which all of the leaves are at the same level, and all of the internal nodes have two children.

A perfect binary tree is a binary tree in which all of the leaves are at the same level, and all of the internal nodes have two children.

Implementing a binary tree.

We will use an auxiliary Node class to store int values and keep references to each child. The first step is to find the place where we want to add the new node in order to keep the tree sorted. To do this, we will follow these rules starting from the root node:

– If the value to be added is smaller than the root value, we will go to the left subtree.

– If the value to be added is larger than the root value, we will go to the right subtree.

– If we reach a leaf node, it means we have found the place to add the new node.

Let’s do the implementation in JavaScript we will use functional programming first:

function BinarySearchTree() { 
 
    var root = null; 

    this.insert = function(value){ 
        if (root === null){ 
            root = new Node(value); 
        } 
        else { 
            insertNode(root, value); 
        } 
    } 

    this.remove = function(value){ 
        root = removeNode(root, value); 
    } 

    this.search = function(value){ 
        return searchNode(root, value); 
    } 

    this.inorder = function(){ 
        inorderTraverseNode(root); 
    } 

    this.preorder = function(){ 
        preorderTraverseNode(root); 
    } 

    this.postorder = function(){ 
        postorderTraverseNode(root); 
    } 

    this.min = function(){ 
        return minNode(root); 
    } 

    this.max = function(){ 
        return maxNode(root); 
    } 
} 

function insertNode(node, newVal) { 
    if (newVal < node.value) { 
        if (node.left === null) { 
            node.left = new Node(newVal); 
        } 
        else { 
            insertNode(node.left, newVal); 
        } 
    } 
    else { 
        if (node.right === null) { 
            node.right = new Node(newVal); 
        } 
        else { 
            insertNode(node.right, newVal); 
        } 
    } 
} 

function removeNode(node, key) { 
    if (node === null) { 
        return null; 
    } 
    if (key < node.value) { 
        node.left = removeNode(node.left, key); 
        return node; 
    } 
    else if (key > node.value) { 
        node.right = removeNode(node.right, key); 
        return node; 
    } 
    else { 
        if (node.left === null && node.right === null) { 
            node = null; 
            return node; 
        } 
        if (node.left === null) { 
            node = node.right; 
            return node; 
        } 
        else if (node.right === null) { 
            node = node.left; 
            return node; 
        } 
        var aux = minNode(node.right); 
        node.value = aux.value; 
        node.right = removeNode(node.right, aux.value); 
        return node; 
    } 
} 

function searchNode(node, key) { 
    if (node === null) { 
        return false; 
    } 
    if (key < node.value) { 
        return searchNode(node.left, key); 
    } 
    else if (key > node.value) { 
        return searchNode(node.right, key); 
    } 
    else { 
        return true; 
    } 
} 

function inorderTraverseNode(node) { 
    if (node !== null) { 
        inorderTraverseNode(node.left); 
        console.log(node.value); 
        inorderTraverseNode(node.right); 
    } 
} 

function preorderTraverseNode(node) { 
    if (node !== null) { 
        console.log(node.value); 
        preorderTraverseNode(node.left); 
        preorderTraverseNode(node.right); 
    } 
} 

function postorderTraverseNode(node) { 
    if (node !== null) { 
        postorderTraverseNode(node.left); 
        postorderTraverseNode(node.right); 
        console.log(node.value); 
    } 
} 

function minNode(node) { 
    if (node) { 
        while (node && node.left !== null) { 
            node = node.left; 
        } 

        return node.value; 
    } 

    return null; 
} 

function maxNode(node) { 
    if (node) { 
        while (node && node.right !== null) { 
            node = node.right; 
        } 

        return node.value; 
    } 
    return null; 
}

Using JavaScript Class

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinaryTree {
  constructor() {
    this.root = null;
  }

  // function to insert a node in the tree
  insert(value) {
    const newNode = new Node(value);

    // if the tree is empty, set the root to the new node
    if (this.root === null) {
      this.root = newNode;
    } else {
      // find the correct position in the tree and insert the new node
      this.insertNode(this.root, newNode);
    }
  }

  // helper function to insert a node in the correct position in the tree
  insertNode(node, newNode) {
    // if the value of the new node is less than the value of the current node, insert it in the left subtree
    if (newNode.value < node.value) {
      // if the left child of the current node is null, set the left child to the new node
      if (node.left === null) {
        node.left = newNode;
      } else {
        // if the left child is not null, recurse through the left subtree
        this.insertNode(node.left, newNode);
      }
    } else {
      // if the value of the new node is greater than or equal to the value of the current node, insert it in the right subtree
      if (node.right === null) {
        node.right = newNode;
      } else {
        // if the right child is not null, recurse through the right subtree
        this.insertNode(node.right, newNode);
      }
    }
  }

  // function to remove a node from the tree
  remove(value) {
    // if the tree is empty, return null
    if (this.root === null) {
      return null;
    } else {
      // find the node to be removed and remove it
      this.root = this.removeNode(this.root, value);
    }
  }

  // helper function to remove a node from the tree
  removeNode(node, value) {
    // if the tree is empty, return null
    if (node === null) {
      return null;
    }

    // if the value to be removed is less than the value of the current node, recurse through the left subtree
    if (value < node.value) {
      node.left = this.removeNode(node.left, value);
      return node;
    } else if (value > node.value) {
      // if the value to be removed is greater than the value of the current node, recurse through the right subtree
      node.right = this.removeNode(node.right, value);
      return node;
    } else {
      // if the value to be removed is equal to the value of the current node, remove the node

      // if the node to be removed has no children, set it to null
      if (node.left === null && node.right === null) {
        node = null;
        return node;
      }

      // if the node to be removed has no left child, set the node to its right child
      if (node.left === null) {
        node = node.right;
        return node;
      } else if (node.right === null) {
        // if the node to be removed has no right child, set the node to its left child
        node = node.left;
        return node;
      }

      // if the node to be removed has two children, find the minimum value in the right subtree
      const minValue = this.findMinValue(node.right);
      node.value = minValue;

      // remove the minimum value from the right subtree
      node.right = this.removeNode(node.right, minValue);
      return node;
    }
  }

  // function to find the minimum value in a subtree
  findMinValue(node) {
    if (node.left === null) {
      return node.value;
    } else {
      return this.findMinValue(node.left);
    }
  }

  // function to search for a value in the tree
  search(value) {
    // if the tree is empty, return false
    if (this.root === null) {
      return false;
    } else {
      // search for the value in the tree
      return this.searchNode(this.root, value);
    }
  }

  // helper function to search for a value in the tree
  searchNode(node, value) {
    // if the tree is empty, return false
    if (node === null) {
      return false;
    }

    // if the value is less than the value of the current node, recurse through the left subtree
    if (value < node.value) {
      return this.searchNode(node.left, value);
    } else if (value > node.value) {
      // if the value is greater than the value of the current node, recurse through the right subtree
      return this.searchNode(node.right, value);
    } else {
      // if the value is equal to the value of the current node, return true
      return true;
    }
  }
}

Solving Leetcode 31. Next Permutation

0

Question from Leetcode.

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

  • For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

  • For example, the next permutation of arr = [1,2,3] is [1,3,2].
  • Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
  • While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

What are they asking?

Let’s break down the question. Leetcode 31(Next Permutation) is asking for the next permutation of an array of integers. A permutation is an arrangement of the members of an array into a sequence. The next permutation is the next lexicographically greater permutation of the array. This means that if the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such an arrangement is not possible, the array must be rearranged as the lowest possible order (i.e. sorted in ascending order).

Solving the problem

There are a few ways to solve this, we will do so in JavaScript & Java:


There are a few solutions to solving Leetcode 31 Next Permutation. One solution is to find the next largest permutation by reversing the order of the elements from the end of the array. Another solution is to find the next smallest permutation by swapping the first and second elements, then reversing the order of the elements from the end of the array.

The most optimal way would be to find the next largest permutation by reversing the order of the elements from the end of the array.

Here is the code in JavaScript:

function nextPermutation(nums) {
  // Start from the second last element in the array and keep track of the largest element found so far
  var i = nums.length - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) {
    i--;
  }
  // If the largest element is not the first element, then swap it with the next largest element
  if (i >= 0) {
    var j = nums.length - 1;
    while (j >= 0 && nums[j] <= nums[i]) {
      j--;
    }
    swap(nums, i, j);
  }
// Reverse the order of the elements from the end of the array
  reverse(nums, i + 1);
  return nums;
}

function swap(nums, i, j) {
  var temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

function reverse(nums, start) {
  var i = start,
    j = nums.length - 1;
  while (i < j) {
    swap(nums, i, j);
    i++;
    j--;
  }
}

The time complexity is O(n) and the space complexity is O(1).

Here is the code in Java:

public class Solution {
    public void nextPermutation(int[] nums) {
        // Start from the second last element in the array and keep track of the largest element found so far
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // If the largest element is not the first element, then swap it with the next largest element
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }

        // Reverse the order of the elements from the end of the array
        reverse(nums, i + 1);
    }
    
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    public void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}

Other Array Problems:

Solving k largest(or smallest) elements in an array.

0

Question: Write an efficient program for printing k largest elements in an array. Elements in an array can be in any order.
For example: if the given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., k = 3 then your program should print 50, 30, and 23.

There are a few different ways to do this. One way would be to keep track of the k largest elements as you iterate through the array, replacing elements in your “k largest” list with larger elements from the array as you encounter them. Another way would be to first sort the array, then print the last k elements.

This is a common Amazon Interview Question.

What is the most efficient way?

The most efficient way would be to keep track of the k largest elements as you iterate through the array, replacing elements in your “k largest” list with larger elements from the array as you encounter them.

Here is one possible implementation in JavaScript:

function printKLargest(arr, k) {
  // create an empty list to track the k largest elements
  var kLargest = [];

  // iterate through the array
  for (var i = 0; i < arr.length; i++) {
    // if the list is not full, simply add the element to the list
    if (kLargest.length < k) {
      kLargest.push(arr[i]);
    }
    // if the list is full, compare the current element to the smallest element in the list
    // if the current element is larger, replace the smallest element with the current element
    else {
      var min = Math.min.apply(null, kLargest);
      if (arr[i] > min) {
        var index = kLargest.indexOf(min);
        kLargest[index] = arr[i];
      }
    }
  }

  // print the k largest elements
  return kLargest;
}
//Driver Code
const args = [30,4,8,8,8];

const ans = printKLargest(args,2)
// Will print [30,8] 2 largest numbers in array
console.log(ans)

Here is the code in Java.

public class printKLargest {
  public static void printKLargest(ArrayList<Integer> arr, int k) {
    // create an empty list to track the k largest elements
    ArrayList<Integer> kLargest = new ArrayList<Integer>();
    // iterate through the array
    for (int i = 0; i < arr.size(); i++) {
      // if the list is not full, simply add the element to the list
      if (kLargest.size() < k) {
        kLargest.add(arr.get(i));
      }
      // if the list is full, compare the current element to the smallest element in the list
      // if the current element is larger, replace the smallest element with the current element
      else {
        int min = Collections.min(kLargest);
        if (arr.get(i) > min) {
          int index = kLargest.indexOf(min);
          kLargest.set(index, arr.get(i));
        }
      }
    }
    // print the k largest elements
    return kLargest;
  }
}

The most efficient way to print the k largest elements in an array is to keep track of the k largest elements as you iterate through the array, replacing elements in your “k largest” list with larger elements from the array as you encounter them.

Calling Functions in JavaScript

Functions are one of the most important building blocks of JavaScript. They allow us to group related code together and make it easier to reuse. In this post, we’ll learn how to call functions in JavaScript. We’ll cover three different types of functions: function declarations, function expressions, and arrow functions. By the end of this post, you’ll have a solid understanding of how to call functions in JavaScript.

Let’s get started!

Function Declarations

A function declaration is a function that is declared at the beginning of a script or within a scope. The function keyword is followed by the name of the function. The function name can be any valid identifier. Function declarations are hoisted, which means they are moved to the top of the current scope before execution. This means that you can call a function before it is declared in the script.

function multiply(a, b) {
  return a* b;
}

console.log(multiply(5, 6));
// expected output: 30

Function Expressions

A function expression is a anonymous function that is assigned to a variable. The function keyword is followed by an optional name. If the function has a name, it can be used to call itself recursively. Function expressions are not hoisted so you must declare the function before you can call it.

const getRectArea = function(width, height) {
  return width * height;
};

console.log(getRectArea(3, 4));
// expected output: 12

Arrow Functions

An arrow function is a shorthand notation for writing anonymous functions. Arrow functions do not have a name so they cannot be referenced elsewhere in your code. Arrow functions are not hoisted so you must declare the function before you can call it.

const foo = (args) =&gt;{
   //Do Something
}
foo(args);

Calling a function as a method

In order to call a function as a method, it must be defined as a property on an object. Let’s look at some code.

obj = {
  foo: function() {
    console.log("boo");
  }
}

var func = obj.foo;

func();

In the above code, we have an object literal with a property named “foo”. The value of the foo property is a function. We can call the function by using the dot notation.

As you can see from the output, calling a function as a method is just like calling any other function.

There are several ways to call functions in JavaScript. Function declarations are hoisted so they can be called before they are declared in the script. Function expressions and arrow functions are not hoisted so they must be declared before they can be called. Each method has its own advantages and disadvantages so choose the one that best suits your needs. Thanks for reading!

Solving Leetcode 39. Combination Sum

0

In this post, we explore a classic coding challenge from Leetcode: problem 39, “Combination Sum.” This problem tests a developer’s ability to find all possible combinations of elements in a given array that add up to a specific target value. We discuss the problem statement in detail, provide an example solution in JavaScript & Java, and discuss some key insights and tips for solving this problem effectively.

From Leetcode:

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

What is the problem asking?

The idea is to use backtracking. We start with an empty list and keep adding elements to it until we reach the target sum. We iterate over all the elements in the array and add them to the list if they don’t exceed the target sum.

We then recursively call the same function with the updated target sum and list. We keep doing this until we either reach the target sum or we run out of elements to add. We then remove the last element from the list and try adding the next element in the array.

We keep doing this until we either reach the target sum or we run out of elements to add. We keep doing this until we either reach the target sum or we run out of elements to add. We then return the list.

One thing to note is that we need to sort the array first in order for this approach to work. This is because, without sorting, there may be cases where we reach the target sum earlier but still have elements left in the array which can lead to duplicate combinations. By sorting the array, we ensure that all possible combinations are explored before moving on to the next element in the array.

Overall, this solution has a time complexity of O(n^m) where n is the length of the candidates array and m is the target sum. This is because at each step, we have n choices and we repeat this process m times until we reach the target sum. The space complexity is O(m) as at each step, we can potentially add a new combination to the output list.

Solving Leetcode 39 in Java:

class Solution {
    public List < List < Integer >> combinationSum(int[] candidates, int target) {
        List < List < Integer >> result = new ArrayList < > ();
        if (candidates == null || candidates.length == 0) {
            return result;
        }

        List < Integer > curr = new ArrayList < > ();
        dfs(candidates, target, 0, curr, result);
        return result;
    }

    private void dfs(int[] candidates, int target, int index, List < Integer > curr, List < List < Integer >> result) {
        if (target == 0) {
            result.add(new ArrayList < > (curr));
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            if (target - candidates[i] >= 0) {
                curr.add(candidates[i]);
                dfs(candidates, target - candidates[i], i, curr, result);
                curr.remove(curr.size() - 1);
            }
        }

    }
}

Solution in JavaScript:

const combinationSum = (candidates, target) => {
  const res = [];
  const dfs = (start, sum, path) => {
    if (sum > target) return;
    if (sum === target) {
      res.push(path.slice());
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i]);
      dfs(i, sum + candidates[i], path);
      path.pop();
    }
  };
  dfs(0, 0, []);
  return res;
};

LeetCode 39 problem is a great challenge for any coding enthusiast. By using a combination of backtracking and recursion, the problem can be solved efficiently. While this approach may not be the most straightforward solution, it is an effective way to find all possible combinations of integers that add up to the target number. With a bit of practice, it can be a great tool to help you master the basics of coding.

Similar Questions:

  • Combinations

Solving Leetcode 54. Spiral Matrix. Spirally traversing a matrix

0

Problem statement

Given an m x n matrix, return all elements of the matrix in spiral order.

This problem seems little tricky but it is very easy to understand once you realize how spiral order works. And this question often comes up on interviews so here’s what I did! In a regular matrix, like the one below where each column represents an element and each row its corresponding multiple of three (3), we can follow four different directions: going right will take us down from any given pointy-ness; moving left brings us closer toward zero while going upward boosts our score by one unit every time – that means

Example I/O

Let’s say we have an input array [[1,2,3],[4,5,6],[7,8,9]]

The expected output is a list of integers in spiral order, that is [1,2,3,6,9,8,7,4,5].

Optimized solution

Let’s remember, we’re dealing with 2D arrays. The most optimized solution to Leetcode 54. Spiral Matrix is to use a single loop that iterates over the matrix and prints out the elements in a clockwise spiral order, as described above. This solution is much more efficient than using multiple nested loops.

Here is the example in JavaScript:

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
        if (!matrix.length) return [];
    let top = 0;
    let bottom = matrix.length - 1;
    let left = 0;
    let right = matrix[0].length - 1;
    const res = [];
    while (true) {
        // go right
        for (let i = left; i <= right; i++) {
            res.push(matrix[top][i]);
        }
        top++;
        if (top > bottom) break;
        // go down
        for (let i = top; i <= bottom; i++) {
            res.push(matrix[i][right]);
        }
        right--;
        if (right < left) break;
        // go left
        for (let i = right; i >= left; i--) {
            res.push(matrix[bottom][i]);
        }
        bottom--;
        if (bottom < top) break;
        // go up
        for (let i = bottom; i >= top; i--) {
            res.push(matrix[i][left]);
        }
        left++;
        if (left > right) break;
    }
    return res;
};
  1. Initialize the result array, and pointers for the top, bottom, left and right edges of the matrix.
  2. While the pointers haven’t crossed over each other:
    • Traverse the top edge of the matrix from left to right.
    • Traverse the right edge of the matrix from top to bottom.
    • Traverse the bottom edge of the matrix from right to left, if top <= bottom.
    • Traverse the left edge of the matrix from bottom to top, if left <= right.
  3. Return the result array

Code in Java:

List<Integer> result = new ArrayList<>();
 if(matrix.length == 0) return result;
 int rowBegin = 0;
 int rowEnd = matrix.length - 1;
 int colBegin = 0;
 int colEnd = matrix[0].length - 1;
 while(rowBegin <= rowEnd && colBegin <= colEnd){
     // Traverse Right
     for(int i = colBegin; i <= colEnd; i++){
         result.add(matrix[rowBegin][i]);
     }
     rowBegin++;
     // Traverse Down
     for(int i = rowBegin; i <= rowEnd; i++){
         result.add(matrix[i][colEnd]);
     }
     colEnd--;
     if(rowBegin <= rowEnd){
         // Traverse Left
         for(int i = colEnd; i >= colBegin; i--){
             result.add(matrix[rowEnd][i]);
         }
     }
     rowEnd--;
     if(colBegin <= colEnd){
         // Traver Up
         for(int i = rowEnd; i >= rowBegin; i--){
             result.add(matrix[i][colBegin]);
         }
     }
     colBegin++;
 }
 return result;

This is an example of the 2-pointer method to traverse the matrix in a spiral order. This approach uses four pointers: top, bottom, left, and right to keep track of the current boundaries of the spiral.

The approach starts by initializing these pointers to the edges of the matrix. The outer while loop keeps track of the overall spiral traversal, and it continues to execute while the top pointer is less than or equal to the bottom pointer and the left pointer is less than or equal to the right pointer.

The first for loop iterates through the top row of the matrix from the left pointer to the right pointer and pushes the elements to the result array. Then, the top pointer is incremented, next inner loop iterates through the rightmost column of the matrix from the top pointer to the bottom pointer and pushes the elements to the result array. The right pointer is decremented.

Then there is an if block to check if top is less than bottom, if it is true it iterates through the bottom row of the matrix from the right pointer to the left pointer and pushes the elements to the result array and decrements the bottom pointer.

Finally, there is another if block to check if left is less than right, if it is true it iterates through the leftmost column of the matrix from the bottom pointer to the top pointer and pushes the elements to the result array and increments the left pointer.

This algorithm visits each element in the matrix exactly once and return the elements in the spiral order.

Time and space complexity

The approach which we used above was the use of a 2-pointer method which goes through the matrix once, visiting each element exactly once. This method takes O(n) time complexity where n is the total number of elements in the matrix. The space complexity is O(1) because we only use a small number of variables to keep track of the current position and direction.

Conclusion:

Solving Leetcode 54, also known as Spiral Matrix, requires traversing a given matrix in a spiral order. There are multiple ways to approach this problem, each with its own advantages and disadvantages. One approach is to use a 2-pointer method (Shown above) to traverse the matrix in a spiral order. Another approach could have been to use a recursion technique. It’s important to note that this is just one of the ways of solving this problem and there may be other solutions as well. In any case, understanding the problem, thinking through the solution, and practicing different approaches are key to solving Leetcode problems such as this one.

Solving Leetcode 24. Swap Nodes in Pairs

0

Problem Stated From Leetcode: Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

Given a linked list:

Before: `[a, b, c, d]`

After : `[b, a, d, c]`

We can solve this problem iteratively or recursively. The idea is that we need to keep track of the previous node and the current node so that we can link them back together after we swap. Let’s look at the iterative solution first:

We create a dummy node to help us keep track of the head (since the head will change after we swap) and set it equal to the current node. We then set up a while loop that will run as long as our current node exists and is not equal to the dummy node (since we don’t want to swap the very first node.) Within the while loop, we set up a temporary variable that will store the value of our current node’s next node. We then set the current node’s next equal to it’s previous node (which we can get by going two nodes back.) Then, we set the previous node’s next equal to our temporary variable (which contains the original next node.) And finally, we update our previous node and current node pointers for the next iteration.

Following Code in Java:

public ListNode swapPairs(ListNode head) {



    if (head == null || head.next == null) return head;



    ListNode dummy = new ListNode(-999);

    dummy.next = head;



    ListNode prev = dummy;

    ListNode curr = head;



    while (curr != null &amp;&amp; curr != dummy) {

        ListNode temp = curr.next;



        curr.next = prev;

        prev.next = temp;



        prev = curr;

        curr = temp;

    }



    // set head and unlink dummy node

    head = dummy.next.next;

    dummy.next.next = null;



    return head;

}

Here is the code also in JavaScript.

/**

 * Definition for singly-linked list.

 * function ListNode(val, next) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.next = (next===undefined ? null : next)

 * }

 */

/**

 * @param {ListNode} head

 * @return {ListNode}

 */

var swapPairs = function(head) {

     if(head === null || head.next === null) {

        return head;

    }

    var dummy = new ListNode(0);

    dummy.next = head;

    var current = dummy;

    while(current.next !== null && current.next.next !== null) {

        var firstNode = current.next;

        var secondNode = current.next.next;

        firstNode.next = secondNode.next;

        current.next = secondNode;

        current.next.next = firstNode;

        current = current.next.next;

    }

    return dummy.next;

};

We can also solve this problem recursively, which may be easier to understand if you are not familiar with linked lists. The idea is that we want to swap the current node with it’s next node, but we need to do this in a way that will work for the rest of the list. So we recursively call the `swapPairs` method on the next node’s next, and then set the current node’s next equal to that. Finally, we set the next node’s next equal to the current node.

Here is the code in Java:

public ListNode swapPairs(ListNode head) {

if (head == null || head.next == null) return head;

// swap with next node

ListNode temp = head.next;

head.next = swapPairs(temp.next);

temp.next = head;

return temp;

}

Both of these solutions run in O(n) time and O(n) space. Hope this helped! Let me know if you have any questions. 🙂

Solving Leetcode 11: Container With Most Water

0

Problem:

From Leetcode

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

From the start we can tell that this is an array question. When it comes to this question it seems that we will be comparing elements with each other. One of the first approach to this problem is to use a double for loop. Unfortunately we know that a double for loop runs in O(N^2) time, which is very inefficient.

2-Pointer Solution

The ideal solution would be to have two pointers, we could call them start and end. The start pointer will start at the beginning of the array (index 0) and the end pointer will start at the end. (height.length -1). Note that we want the index of the array start and end, NOT the element.

Next we know that by starting at each end we can check whether or not the previous or next element is higher or or not. If so we set the new pointer to higher element and update the area.

  1. Keep two index, start= 0 and end = n-1 and a value area that stores the maximum area.
  2. Run a while loop until first is less than the last.
  3. Update the area with maximum of area and min(array[first] , array[last])*(last-first)
  4. if the value at array[first] is greater the array[last] then update last as last – 1 else update first as first + 1
  5. Print the maximum area.

Code Here:

class Solution {
    public int maxArea(int[] height) {

        int area = 0;

        int start = 0;

        int end = height.length - 1;

        while(start &lt; end){
            int top = Math.min(height[start], height[end]);

            int newArea = top*(end-start);
            area = Math.max(area, newArea);

            if(height[start]&lt; height[end]){
                start++;
            }
            else{
                end--;
            }
        }
     return area;   
    }
}

We can find the maximum area under a histogram using two pointers. The pointers start at the beginning and end of the histogram, and we move them inward until they meet. At each step, we calculate the area of the rectangle formed by the two pointers and the current height of the histogram. The maximum area is the largest area we calculate.

This algorithm is simple to implement and has a time complexity of O(n). It is a good choice for finding the maximum area under a histogram when the histogram is large.