The ultimate guide to coding interviews. Developed by FAANG engineers. Boost problem-solving skills with number theory, dynamic programming, and graph theory. Get interview-ready in just a few hours.

Competitive Programming - Crack Your Coding Interview.png

Whether you’re gearing up for online coding challenges, code-a-thons, or interviews, then this course is for you. With this course, you will solidify your problem-solving skills ensuring a swift sail through any problem. 


You will be tasked with solving some of the most frequently asked questions that are brought up in FAANG interviews. You will start with the concepts of Number Theory and Divide and Conquer, and gradually move towards more complex problems like dynamic programming and graph theory.


With each problem you solve, there will be insightful explanations and full implementation details to really hammer home the concepts. By the time you finish this course, you will have the confidence to solve any problem, no matter the difficulty.

Competitive Programming - Crack Your Coding Interview, C++

# Problem statement
The problem in this lesson tries to solve the following type of question:
> *Finding the number of ways to reach from a starting position to an ending position when traveling in specified directions only.*

The problem statement is: 

**Given a 2-D matrix with `M` rows and `N` columns, find the number of ways to reach the cell with coordinates (i, j) from the starting cell (0, 0) under the condition that you can only travel one step right or one step down.**

This problem is very similar to the previous one. To reach a cell **(i, j)**, one must first reach either the cell **(i-1, j)** or the cell **(i, j-1)**, and then move one step down or to the right respectively to reach cell **(i, j)**.


# Solution: **Dynamic programming approach**

This problem indeed satisfies the optimal substructure and overlapping
subproblems properties, so we need to try and formulate a dynamic programming solution.

Let `numWays(i, j)` be the number of ways to reach position **(i, j)**. As stated above, the number of ways to
reach cell **(i, j)** will be equal to the sum of the number of ways of reaching **(i-1, j)** and the number of ways of reaching **(i, j-1)**. Thus, we get the following recurrence relation:

**numWays(i, j) = numWays(i-1, j) + numWays(i, j-1)** 

Let's move to the implementation now.


Learn to use medium to difficult grid-based problems with dynamic programming.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Problems Involving Grids - 2

Problem statement