This is a study record of Ray Tracing in One Weekend.

Output My First Image

PPM Image format

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>

int main() {

    // Image

    int image_width = 256;
    int image_height = 256;

    // Render

    std::cout << "P3\n" << image_width << ' ' << image_height << "\n255\n";

    for (int j = 0; j < image_height; ++j) {
        for (int i = 0; i < image_width; ++i) {
            auto r = double(i) / (image_width-1);
            auto g = double(j) / (image_height-1);
            auto b = 0;

            int ir = static_cast<int>(255.999 * r);
            int ig = static_cast<int>(255.999 * g);
            int ib = static_cast<int>(255.999 * b);

            std::cout << ir << ' ' << ig << ' ' << ib << '\n';
        }
    }
}

• static_cast<int> is used to convert double to int

The output is a text content, shows something like:

1
2
3
4
5
6
7

P3
256 256
255
0 0 0
1 0 0
2 0 0
3 0 0

The P3 means colours are in ASCII. The columns number is 256, and the rows number is 256. The max colour is 255.

Redirect to an image file

To view the image directly, we need to redirect the output file like this:
./helloworld > image.ppm .
./helloworld is the name of my output c++ file, and image.ppm is the image file.
The result of image.ppm looks like this:

Since the rows are written from top to bottom, and columns are written from left to right, it makes sense that the top left is dark and the bottom right is black.

Adding a Progress Indicator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

for (int j = 0; j < image_height; ++j) {
    // Adding Progress Indicator
    std::clog << "\rScanlines remaining: " << (image_height - j) << ' ' << std::flush; 
    for (int i = 0; i < image_width; ++i) {
        auto r = double(i) / (image_width-1);
        auto g = double(j) / (image_height-1);
        auto b = 0;

        int ir = static_cast<int>(255.999 * r);
        int ig = static_cast<int>(255.999 * g);
        int ib = static_cast<int>(255.999 * b);

        std::cout << ir << ' ' << ig << ' ' << ib << '\n';
    }
}
std::clog << "\rDone.                 \n";

Since the program outputs the image to the standard output stream std::cout, we use std::clog to record our progress. The output of std::clog is stored in a buffer until the buffer is flushed.

std::flush forces the buffered output in std::clog to be immediately written to its output (usually to the terminal).

Setting Vec3 Class

We create a vec3.h file to define the class vec3, and then include it in the main file.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

#ifndef VEC3_H
#define VEC3_H

#include <cmath>
#include <iostream>

using std::sqrt;

class vec3
{
public:
    // defines an arry named 'e' of size 3, and each element's type is double
    double e[3];
    // initialise the elements of the array e with 0
    vec3() : e{0, 0, 0} {}
    vec3(double e0, double e1, double e2) : e{e0, e1, e2} {}

    double x() const { return e[0]; }
    double y() const { return e[1]; }
    double z() const { return e[2]; }

    // negations of the vector
    vec3 operator-() const { return vec3(-e[0], -e[1], -e[2]); }
    double operator[](int i) const { return e[i]; }
    double &operator[](int i) { return e[i]; }

    vec3 &operator+=(const vec3 &v)
    {
        e[0] += v.e[0];
        e[1] += v.e[1];
        e[2] += v.e[2];
        return *this;
    }

    vec3 &operator*=(double t)
    {
        e[0] *= t;
        e[1] *= t;
        e[2] *= t;
        return *this;
    }

    vec3 &operator/=(double t)
    {
        return *this *= 1 / t;
    }

    double length() const
    {
        return sqrt(length_squared());
    }

    double length_squared() const
    {
        return e[0] * e[0] + e[1] * e[1] + e[2] * e[2];
    }
};

// alias for vec3, for geometric clarity
using point3 = vec3;

// Vector Utility Functions

inline std::ostream &operator<<(std::ostream &out, const vec3 &v)
{
    return out << v.e[0] << ' ' << v.e[1] << ' ' << v.e[2];
}

inline vec3 operator+(const vec3 &u, const vec3 &v)
{
    return vec3(u.e[0] + v.e[0], u.e[1] + v.e[1], u.e[2] + v.e[2]);
}

inline vec3 operator-(const vec3 &u, const vec3 &v)
{
    return vec3(u.e[0] - v.e[0], u.e[1] - v.e[1], u.e[2] - v.e[2]);
}

inline vec3 operator*(double t, const vec3 &v)
{
    return vec3(t * v.e[0], t * v.e[1], t * v.e[2]);
}

inline vec3 operator*(const vec3 &v, double t)
{
    return t * v;
}

inline vec3 operator/(vec3 v, double t)
{
    return (1 / t) * v;
}

inline double dot(const vec3 &u, const vec3 &v)
{
    return u.e[0] * v.e[0] + u.e[1] * v.e[1] + u.e[2] * v.e[2];
}

inline vec3 cross(const vec3 &u, const vec3 &v)
{
    return vec3(u.e[1] * v.e[2] - u.e[2] * v.e[1],
                u.e[2] * v.e[0] - u.e[0] * v.e[2],
                u.e[0] * v.e[1] - u.e[1] * v.e[0]);
}

inline vec3 unit_vector(vec3 v)
{
    return v / v.length();
}

#endif

Color Utility Functions

We create a color.h file to define the color class, and then include it in the main file. It is worth to note that the color class is an alias for the vec3 class, so there is no main difference between the two classes but we can recognize the color class more easily.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#ifndef COLOR_H
#define COLOR_H

#include "vec3.h"

#include <iostream>

using color = vec3;

void write_color(std::ostream &out, color pixel_color)
{
    // Write the translated [0, 255] of each color component
    out << static_cast<int>(259.99 * pixel_color.x()) << ' '
        << static_cast<int>(259.99 * pixel_color.y()) << ' '
        << static_cast<int>(259.99 * pixel_color.z()) << '\n';
}
#endif

Rewrite our main file

After we have defined the vec3 class and the color class, we can rewrite our main file like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include "vec3.h"
#include "color.h"

#include <iostream>

int main()
{
    int image_width = 256;
    int image_height = 256;

    std::cout << "P3\n"
              << image_width << ' ' << image_height << "\n255\n";

    for (int j = 0; j < image_height; ++j)
    {
        std::clog << "\rScanlines remaining: " << (image_height - j) << ' ' << std::flush;
        for (int i = 0; i < image_width; ++i)
        {
            auto pixel_color = color(double(i) / (image_width - 1), double(j) / (image_height - 1), 0);
            write_color(std::cout, pixel_color);
        }
    }
    std::clog << "\rDone.                  \n";
}

Ray

Ray Class

We create a ray.h file to define the ray class. The ray class has two member variables: orig and dir, which are the origin and direction of the ray, respectively. The at method returns the point at the parameter t along the ray.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#ifndef RAY_H
#define RAY_H

#include "vec3.h"

class ray {
    public:
        ray() {}

        // Initializes the member variables orig and dir of the ray object with the values passed to the constructor. 
        ray(const point3& origin, const vec3& direction): orig(origin), dir(direction){}

        point3 origin() const {return orig;}
        vec3 direction() const {return dir;}

        point3 at(double t) const{
            return orig + t * dir;
        }
    
    private:
        point3 orig;
        vec3 dir;
};

#endif

Sending Rays into the Scene

Viewport: a virtual rectangle in the 3D world that contains the grid of image pixel locations.

If pixels are spaced the same distance horizontally as they are vertically, the viewport that bounds them will have the same aspect ratio as the rendered image.

Pixel spacing: the distance between two adjacent pixels, and square pixels is the standard.

Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4
 
Constraints:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums contains distinct values sorted in ascending order.
-10^4 <= target <= 10^4

Binary Search Solution

We first initialise two pointers, left and right. left is the index of the first element in the array, right is the index of the last element in the array. Then we iterate through the array and update the left and right pointers. If the target is found, we return the index. If the target is not found, we return the index where it would be if it were inserted in order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n-1;
        while(left < right){
            int m = left + (right - left)/2;
            if (nums[m] == target)
                return m;
            else if (nums[m] > target){
                right = m;
            }
            else left= m + 1;
        }
        return nums[left] < target ? left + 1: left;
    }
};

Search a 2D Matrix

You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

1
2
3

Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

1
2

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Binary Search Solution

We use binary search twice to find the answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int top = 0;
        int bottom = m - 1;
        while (top <= bottom){
            int m = top+ (bottom-top)/2;
            if (matrix[m][0] < target)
                top = m + 1;
            else if (matrix[m][0] > target)
                bottom = m - 1;
            else 
                return true;
        }
        int row = bottom;
        if (row < 0) return false;
        for (int left = 0, right = n - 1; left <= right;){
            int middle = left + (right-left) / 2;
            if(matrix[row][middle] < target)
                left = middle + 1;
            else if (matrix[row][middle] > target)
                right = middle - 1;
            else 
                return true;
        }
        return false;
    }
};

Search in Rotated Sorted Array

Description

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:

Input: nums = [1], target = 0
Output: -1
 

Constraints:

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-104 <= target <= 104

Solution

If we treat the question as a normal ascending order array, we can use binary search to deal with it easily. For this problem, we need to first check whether the middle element and the the target are in the same half of the array. If they are, we can use the normal binary search. If they are not, we need to check whether the target is in the left half or the right half of the array. If it is in the left half, we can then set the middle and right half part to infinity, and if it is in the right half, we can set the left half part to negative infinity. Then we can use the normal binary search to find the target.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n - 1;
        while (left <= right){
            int middle = left + (right - left) / 2;
            int comparator = nums[middle];
            // if middle and target are on the same side
            if ((nums[middle] >= nums[0] && target >= nums[0]) || (nums[middle] < nums[0] && target < nums[0])){
                comparator = nums[middle];
            }
            else{
                if (target >= nums[0]){
                    comparator = INT_MAX;
                }
                else{
                    comparator = INT_MIN;
                }
            }
            if (target == comparator)
                return middle;
            if (target > comparator){
                left = middle + 1;
            }
            else if (target < comparator){
                right = middle - 1;
            }
        }
        return -1;
    }
};

Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

My solution

My solution is to initialise two variables, one is the currentMax, the other is the globalMax. currentMax is the maximum sum of the subarray that ends at the current index. globalMax is the maximum sum of the subarray that ends at any index. Then I iterate through the array and update the currentMax and globalMax at each index. Finally, I return the globalMax.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int currentMax = nums[0];
        int globalMax = nums[0];
        for (int i = 1; i < nums.size(); i++){
            int currentElement = nums[i];
            currentMax = max(currentMax + currentElement, currentElement);
            globalMax = max (currentMax, globalMax);
        }
        return globalMax;
    }
};

Maximum Sum Circular Subarray

Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.

A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].

A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], …, nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Example 1:
Input: nums = [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3

Example 2:
Input: nums = [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Example 3:
Input: nums = [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Solution

In this code, we use Kadane’s algorithm to find the maximum subarray sum. Then we find the minimum subarray sum using Kadane’s algorithm on the uninverted array. The maximum wrap sum is the total sum minus the minimum subarray sum. Finally, we return the maximum of the globalMax and maxWrap.

Total Sum: This is the sum of all elements in the array.

Minimum Subarray Sum: This is the smallest possible sum of a contiguous subarray within the array. By finding the minimum subarray sum, you are effectively finding the part of the array that would “cost” you the least if you were to exclude it from the total sum.

Maximum Wrapping Subarray Sum: The maximum sum of a wrapping subarray is essentially the total sum of the array minus some contiguous segment that you exclude. Now, if you want to maximize the sum of the remaining subarray (which wraps around), you should exclude the segment that has the minimum sum. This is because excluding a segment with a larger sum would leave you with a smaller sum for the wrapping subarray.

Therefore, the maximum wrapping subarray sum can be calculated by subtracting the minimum subarray sum from the total sum of the array. This approach works as long as there is at least one element that is not part of the minimum sum subarray. This is why you need to check if the maximum subarray sum found by Kadane’s algorithm is negative: if it is, the entire array consists of negative elements, and thus, you cannot apply this wrapping logic.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int currentMax = nums[0];
        int globalMax = nums[0];
        int totalSum = nums[0];
        
        // Start from the first element for max subarray sum
        for (int i = 1; i < nums.size(); i++) {
            currentMax = max(nums[i], currentMax + nums[i]);
            globalMax = max(globalMax, currentMax);
            totalSum += nums[i]; // sum up all elements
        }
        
        // If all numbers are negative, return globalMax
        if(globalMax < 0) {
            return globalMax;
        }
        
        // Now find the minimum subarray sum using Kadane's algorithm on the uninverted array
        int currentMin = nums[0];
        int globalMin = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            currentMin = min(nums[i], currentMin + nums[i]);
            globalMin = min(globalMin, currentMin);
        }

        // The maximum wrap sum is the total sum minus the minimum subarray sum
        int maxWrap = totalSum - globalMin;

        return max(globalMax, maxWrap);
    }
};

Sort List

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

1
2

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

1
2

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

1
2
3
4
5
6
7
8

Example 3:

Input: head = []
Output: []

Constraints:
The number of nodes in the list is in the range [0, 5 * 104].
-105 <= Node.val <= 105

My solution

My solution actually doesn’t apply the divide and conquer method. I push each value in the node into a list and then sort it first. Then I create a new linked list and push the sorted list into the linked list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr)
            return head;
        vector <int> storeValue;
        ListNode * current = head;
        while(current != nullptr){
            storeValue.push_back(current->val);
            current = current->next;
        }
        sort(storeValue.begin(), storeValue.end());
        ListNode * newHead = new ListNode(storeValue[0]);
        ListNode * newCurrent = newHead;
        for (int i = 1; i < storeValue.size(); i++){
            ListNode * nextNode = new ListNode(storeValue[i]);
            newCurrent -> next= nextNode;
            newCurrent = newCurrent -> next;
        }
        return newHead;
    }
};

Divide and Conquer

I found one good explanation from the LeetCode.

The idea is:

1
2
3

1. Using 2pointer / fast-slow pointer find the middle node of the list.
2. Now call mergeSort for 2 halves.
3. Merge the Sort List (divide and conqueror Approach)

The code is :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        //If List Contain a Single or 0 Node
        if(head == NULL || head ->next == NULL)
            return head;
        
        
        ListNode *temp = NULL;
        ListNode *slow = head;
        ListNode *fast = head;
        
        // 2 pointer appraoach / turtle-hare Algorithm (Finding the middle element)
        while(fast !=  NULL && fast -> next != NULL)
        {
            temp = slow;
            slow = slow->next;          //slow increment by 1
            fast = fast ->next ->next;  //fast incremented by 2
            
        }   
        temp -> next = NULL;            //end of first left half
        
        ListNode* l1 = sortList(head);    //left half recursive call
        ListNode* l2 = sortList(slow);    //right half recursive call
        
        return mergelist(l1, l2);         //mergelist Function call
            
    }
    
    //MergeSort Function O(n*logn)
    ListNode* mergelist(ListNode *l1, ListNode *l2)
    {
        ListNode *ptr = new ListNode(0);
        ListNode *curr = ptr;
        
        while(l1 != NULL && l2 != NULL)
        {
            if(l1->val <= l2->val)
            {
                curr -> next = l1;
                l1 = l1 -> next;
            }
            else
            {
                curr -> next = l2;
                l2 = l2 -> next;
            }
        
        curr = curr ->next;
        
        }
        
        //for unqual length linked list
        
        if(l1 != NULL)
        {
            curr -> next = l1;
            l1 = l1->next;
        }
        
        if(l2 != NULL)
        {
            curr -> next = l2;
            l2 = l2 ->next;
        }
        
        return ptr->next;
    }
};

Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a
height-balanced binary search tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Example 1:


Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:


Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.
 

Constraints:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in a strictly increasing order.

Solution

We use a recursion method to create the tree. Firstly, we find the median of the array and create a node with the median. Then we call the function recursively to create the left and right subtree. The left subtree is created by the left half of the array and the right subtree is created by the right half of the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()) return nullptr;
        int medianInd = nums.size() / 2;
        TreeNode* root = new TreeNode(nums[medianInd]);
        vector<int> left(nums.begin(),nums.begin()+medianInd);
        vector<int> right(nums.begin()+medianInd+1,nums.end());
        root -> left = sortedArrayToBST(left);
        root -> right = sortedArrayToBST(right);
        return root;
    }
};

N-Queens II

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Example 1:


Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.
Example 2:

Input: n = 1
Output: 1
 

Constraints:

1 <= n <= 9

Solution

This is a backtracking problem. We can use a vector to store the position of the queens. The index of the vector represents the row and the value represents the column. We can use a function to check if the current position is valid. If it is valid, we can add it to the vector and call the function recursively. If the size of the vector is equal to n, we can add it to the result. Otherwise, we can remove the last element of the vector and try another position.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    bool isSafe(vector <int> board, int row, int col, int n){
        for(int i = 0; i < row; i++){
            if (board[i] == col or abs(board[i] - col) == abs(i - row))
                return false; 
        }
        return true;
    }
    int solveNQueens(vector <int> board, int row, int n, int count){
        if (row == n){
            count ++;
            return count;
        }
        for (int col = 0; col < n; col++){
            if (isSafe(board, row, col, n)){
                board[row] = col;
                count = solveNQueens(board, row + 1, n, count);
                board[row] = - 1;
            }
        }
        return count;
    }
    int totalNQueens(int n) {
        vector <int> board (n, -1);
        int count = 0;
        return solveNQueens(board, 0, n, count);
    }
};

Variable explanation

In the N-Queens solution, the board array and the row and col variables in the recursion have specific meanings that are crucial to understanding how the algorithm works. Let’s clarify these:

1. The board Array:

   • The board array is a 1D vector of size n, where n is the size of the chessboard (n x n).
   • Each element of the board array represents a row on the chessboard.
   • The value stored at each index of the board array represents the column position where a queen is placed in that row.
   • For example, if board[2] = 3, it means that in row 2, a queen is placed in column 3.

2. The row Variable:

   • The row variable in the solveNQueens function represents the current row on the chessboard where you are trying to place a queen.
   • It is used to iterate through the rows of the chessboard, starting from 0 up to n-1.

3. The col Variable:

   • The col variable in the solveNQueens function represents the column position in the current row where you are attempting to place a queen.
   • For each row, you try placing a queen in each column (from 0 to n-1) and check if it’s a safe placement.

4. The isSafe Function:

   • This function checks whether placing a queen at the board[row] = col position is safe.
   • It checks for conflicts with queens in previous rows. There are two types of conflicts:
     • Column conflict: If any previous row (i) has a queen in the same column (board[i] == col).
     • Diagonal conflict: If any previous row (i) has a queen positioned diagonally. This is checked by the condition abs(board[i] - col) == abs(i - row).

5. Backtracking and Recursion:

   • The solveNQueens function uses recursion to try placing queens row by row.
   • If a safe position is found for a queen in the current row, it moves to the next row.
   • If no safe position is found in a row, it backtracks (i.e., it goes back to the previous row and tries a different column for the queen in that row).

In summary, the board array is a compact way to represent the positions of queens on the chessboard, and the row and col variables are used to navigate through the chessboard to place the queens safely. The algorithm explores all possible ways to place the queens, backtracking when necessary, until all solutions are found.

Combinations

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Example 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
Example 2:

Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.
 

Constraints:

1 <= n <= 20
1 <= k <= n

Solution

To solve this problem, we can use a technique called backtracking, which is a form of recursion. Backtracking is particularly useful for problems where you need to explore multiple possibilities and combinations, like in this case where we want to find all possible combinations of k numbers from the range [1, n].

In this backtracking function, if the combination has k numbers, add it to the result and return. Iterate from the current number to n and recursively call the function with the next number. Backtrack: Remove the last added number to try a new combination.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function combine(n, k):
    result = []

    function backtrack(start, combination):
        if length(combination) == k:
            result.add(combination.copy())
            return

        for i from start to n:
            combination.add(i)
            backtrack(i + 1, combination)
            combination.removeLast()

    backtrack(1, [])
    return result

Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:

Input: nums = [1]
Output: [[1]]
 

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

Solution

The key difference between combinations and permutations is that in permutations, the order matters. Therefore, I need to ensure that each number is used exactly once in each permutation, but in every possible order.

To check if a number is already used in the current permutation, I use a bool array to record each number’s status. If the number is used, I skip it. After call the recursion function, I pop the last number from the current permutation to try the next number and change the status of the current number to unused.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    vector<vector<int>>  ans;
    void backtrack(int index, vector<int> & single, vector<int> nums, vector<bool>& used){
        if (single.size() == nums.size()){
            ans.push_back(single);
            return;
        }
        for (int i = 0; i < nums.size(); i++){
            if (used[i]) continue;
            used[i] = true;
            single.push_back(nums[i]);
            backtrack(index + 1, single, nums, used);
            single.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> single;
        vector<bool> used(nums.size(), false); // To keep track of used elements
        backtrack(0, single, nums, used);
        return ans;
    }
};

Word Search II

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Example 1:


Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
Example 2:


Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
 

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] is a lowercase English letter.
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
All the strings of words are unique.

Solution

This question is like a combination of island question and prefix tree. Let’s explain the code line by line:

This C++ code defines a class Solution that implements a solution to the “Word Search II” problem using a Trie data structure and Depth-First Search (DFS). The problem involves finding all words from a given list that can be formed by sequentially adjacent letters on a board.

1
2
3
4
5
6
7
8
9
10

struct TrieNode {
    TrieNode *children[26];
    string word;

    TrieNode() : word("") {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};

• This is a definition of a TrieNode structure. Each node has 26 children (one for each letter of the alphabet) and a string word. The constructor initializes word to an empty string and all children pointers to nullptr.

1

vector<string> findWords(vector<vector<char>> &board, vector<string> &words) {

• This function, findWords, is the main function of the class. It takes a 2D character vector board and a vector of strings words as input.

1

TrieNode *root = buildTrie(words);

• Here, a Trie is built from the list of words using the buildTrie function.

1

vector<string> result;

• This line initializes a vector result to store the words found on the board.

1
2
3
4
5

for (int i = 0; i < board.size(); i++) {
    for (int j = 0; j < board[0].size(); j++) {
        dfs(board, i, j, root, result);
    }
}

• These lines iterate over each cell of the board and call the dfs (Depth-First Search) function for each cell.

1
2

    return result;
}

• Returns the vector result containing all the words found on the board.

1

TrieNode *buildTrie(vector<string> &words) {

• This function, buildTrie, creates a Trie from the given list of words.

1

TrieNode *root = new TrieNode();

• Creates a new TrieNode that will serve as the root of the Trie.

1
2
3
4
5
6
7
8
9
10
11
12

for (int j = 0; j < words.size(); j++) {
    string word = words[j];
    TrieNode *curr = root;
    for (int i = 0; i < word.length(); i++) {
        char c = word[i] - 'a';
        if (curr->children[c] == nullptr) {
            curr->children[c] = new TrieNode();
        }
        curr = curr->children[c];
    }
    curr->word = word;
}

• This loop inserts each word into the Trie. For each character in a word, it checks if the corresponding child node exists; if not, it creates a new node. After inserting all characters of a word, it sets the word field of the last node.

1
2

    return root;
}

• Returns the root of the Trie.

1

void dfs(vector<vector<char>> &board, int i, int j, TrieNode *p, vector<string> &result) {

• This function, dfs, performs a depth-first search on the board starting from the cell (i, j).

1
2

char c = board[i][j];
if (c == '#' || !p->children[c - 'a']) return;

• This checks if the current cell is already visited (marked as ‘#’) or if there is no child in the Trie corresponding to the current character. If either is true, it returns immediately.

1

p = p->children[c - 'a'];

• Moves to the child node corresponding to the current character.

1
2
3
4

if (p->word.size() > 0) {
    result.push_back(p->word);
    p->word = "";
}

• If the current Trie node has a word (i.e., we have found a word), it adds the word to the result and clears the word in the Trie node to avoid duplicates.

1

board[i][j] = '#';

• Marks the current cell as visited.

1
2
3
4

if (i > 0) dfs(board, i - 1, j, p, result);
if (j > 0) dfs(board, i, j - 1, p, result);
if (i < board.size() - 1) dfs(board, i + 1, j, p, result);
if (j < board[0].size() - 1) dfs(board, i, j + 1, p, result);

• These lines recursively call dfs for all four adjacent cells (up, left, down, right), if they are within the bounds of the board.

1
2

    board[i][j] = c;
}

• Restores the current cell’s original character (unmarking it as visited).

This code efficiently searches for words on a board using Trie and DFS, which is a great demonstration of your understanding of advanced data structures and algorithms.

How Word stored in Trie

In the given implementation of the Trie (prefix tree), the complete word is stored in the last node of its corresponding path. Here’s how it works:

1. Trie Structure: Each node in the Trie represents a single character. The root node typically represents an empty string, and each path from the root to a node represents a prefix of some word.

2. Storing Words: As you insert a word into the Trie, you create a path where each character of the word corresponds to a node. When you reach the end of the word, you store the entire word at the last node in this path.

3. Why Store the Whole Word: Storing the entire word at the last node is particularly useful for applications like the word search problem. When you traverse the Trie during the search, reaching a node with a non-empty word field immediately tells you that you’ve found a valid word. This approach eliminates the need to reconstruct the word from the path you’ve traversed.

4. Example: Suppose you insert the word “cat” into an empty Trie. You’ll create nodes for ‘c’, ‘a’, and ‘t’. At the ‘t’ node, you’ll store the entire word “cat”. If you later insert “car”, you’ll add an ‘r’ node after the ‘a’ node (which is shared with “cat”), and store “car” at the ‘r’ node.

This method is efficient for word search problems because it allows for quick and direct identification of complete words during the traversal of the Trie.

Full code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

class Solution {
    struct TrieNode {
        TrieNode *children[26];
        string word;

        TrieNode() : word("") {
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
        }
    };

public:
    vector<string> findWords(vector<vector<char>> &board, vector<string> &words) {
        TrieNode *root = buildTrie(words);
        vector<string> result;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                dfs(board, i, j, root, result);
            }
        }
        return result;
    }

    /** Inserts a word into the trie. */
    TrieNode *buildTrie(vector<string> &words) {
        TrieNode *root = new TrieNode();
        for (int j = 0; j < words.size(); j++) {
            string word = words[j];
            TrieNode *curr = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word[i] - 'a';
                if (curr->children[c] == nullptr) {
                    curr->children[c] = new TrieNode();
                }
                curr = curr->children[c];
            }
            curr->word = word;
        }
        return root;
    }

    void dfs(vector<vector<char>> &board, int i, int j, TrieNode *p, vector<string> &result) {
        char c = board[i][j];
        if (c == '#' || !p->children[c - 'a']) return;
        p = p->children[c - 'a'];
        if (p->word.size() > 0) {
            result.push_back(p->word);
            p->word = "";
        }

        board[i][j] = '#';
        if (i > 0) dfs(board, i - 1, j, p, result);
        if (j > 0) dfs(board, i, j - 1, p, result);
        if (i < board.size() - 1) dfs(board, i + 1, j, p, result);
        if (j < board[0].size() - 1) dfs(board, i, j + 1, p, result);
        board[i][j] = c;
    }
};

Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:

Input: digits = ""
Output: []
Example 3:

Input: digits = "2"
Output: ["a","b","c"]
 

Constraints:

0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].

My solution

My solution is to use a recursive function with index as the parameter. When the index is equal to the length of the digits, we append the current string to the result. Otherwise, we loop through the letters of the current digit and call the recursive function with the next index.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
public:
    vector<string> ans;
    unordered_map <char, vector<char>> numLetter;

    void recursion(string current, int index, string digits){
        if (index == digits.size()){
            ans.push_back(current);
            return;          
        }
        else{
            for(int i = 0; i< numLetter[digits[index]].size(); i++){
                current += numLetter[digits[index]][i];
                recursion(current, index+1, digits);
                current.pop_back();
            }
        }
    }
    vector<string> letterCombinations(string digits) {
        if (digits == "") return ans;
        string current = "";
        numLetter['2'] = {'a', 'b', 'c'};
        numLetter['3'] = {'d', 'e', 'f'};
        numLetter['4'] = {'g', 'h', 'i'};
        numLetter['5'] = {'j', 'k', 'l'};
        numLetter['6'] = {'m', 'n', 'o'};
        numLetter['7'] = {'p', 'q', 'r','s'};
        numLetter['8'] = {'t', 'u', 'v'};
        numLetter['9'] = {'w', 'x', 'y', 'z'};
        recursion(current, 0, digits);
        return ans;
    }
};