DEV Community

Abhishek Sharma Gaur
Abhishek Sharma Gaur

Posted on

Leetcode 935: Knight Dialer

Intuition

LeetCode Problem: Knight Dialer
Problem Description:
The problem is to find the number of different sequences a knight can make on a dial pad after making n moves. The knight can move to any of the valid digits based on its current position on the dial pad.

Approach:

The given solution uses dynamic programming to iteratively calculate the number of sequences for each digit after making a move. The sequences are updated in each iteration based on the knight's valid moves.

Initialization:

arr = Array.new(10, 1): This initializes an array arr with 10 elements, each initialized to 1. The array represents the count of sequences for each digit.
Iterative Calculation:

(n - 1).times do: This loop iterates n - 1 times, as the initial state already represents the sequences after the first move.
Inside the loop:
A temporary array tmp is created to store the updated counts for each digit based on the knight's moves.
The arr array is then updated with the values from tmp.
Return Result:

The final result is the sum of all sequences in the arr array, and it is returned modulo (10**9 + 7) to avoid integer overflow.

Complexity

  • Time Complexity: The time complexity of this solution is O(n), where n is the number of moves. The loop runs n - 1 times, and the operations inside the loop take constant time.

The space complexity is O(1), as the solution uses a constant amount of space regardless of the input size. The size of the arr array remains constant, and the tmp array is created within the loop.

# @param {Integer} n
# @return {Integer}
def knight_dialer(n)
    arr = Array.new(10, 1)

    (n - 1).times do
      tmp = [
        arr[4] + arr[6],
        arr[6] + arr[8],
        arr[7] + arr[9],
        arr[4] + arr[8],
        arr[3] + arr[9] + arr[0],
        0,
        arr[1] + arr[7] + arr[0],
        arr[2] + arr[6],
        arr[1] + arr[3],
        arr[2] + arr[4]
      ]

      arr = tmp
    end

    return arr.sum % (10**9 + 7)
end
Enter fullscreen mode Exit fullscreen mode

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay