Dynamic_Array_Exercise Class Reference

#include <leetcode_practice.h>

Public Member Functions
int	pivot (vector< int > &nums)
	Find the pivot index - Easy. More...
int	dominantIndex (vector< int > &nums)
	Find the index of largest number At Least Twice of Others - Easy. More...
vector< int >	plusOne (vector< int > &nums)
	Plus one the last position - Easy. More...
vector< int >	findDiagonalOrder (vector< vector< int >> &matrix)
	Diagonal Order - Medium. More...
vector< int >	spiralMatrix (vector< vector< int >> &matrix)
	Print Spiral Matrix - Medium. More...
vector< vector< int > >	pachiraTringle (int numRows)
	Print Pascal's triangle - Easy. More...
int	numEquivDominoPairs (vector< vector< int >> &dominoes)
	Number of Equivalent dominoes Pairs - Easy. More...
int	numEquivDominoPairs_opt (vector< vector< int >> &dominoes)
	Optimized Number of Equivalent dominoes Pairs - Easy. More...

Member Function Documentation

dominantIndex()

int Dynamic_Array_Exercise::dominantIndex

(

vector< int > &

nums

)

Find the index of largest number At Least Twice of Others - Easy.

Parameters

The	test case's vector

Returns

The index of largest number

Ideal:

1. Find the index of max value
2. Determine whether the largest number is at least twice of others and avoid to scan on the current index

{
    int maxIndex = 0;

    // Find the index of max value
    for (int i = 0; i < nums.size(); ++ i)
        if (nums[i] < nums[maxIndex])
            maxIndex = i;

    // Fail situation, otherwise the index of largest number is at least twice of others
    for (int j = 0; j < nums.size(); ++ j) {
        if (nums[maxIndex] < 2 * nums[j] && maxIndex != j)
            return -1;
    }

    return maxIndex;
}

Referenced by leetcode_practice().

findDiagonalOrder()

vector< int > Dynamic_Array_Exercise::findDiagonalOrder

(

vector< vector< int >> &

matrix

)

Diagonal Order - Medium.

Parameters

The	test case's matrix

Returns

The diagonal order's matrix

Ideal:

1. Using the direction map to indicate the route's direction
2. Avoid out-of-range
3. Storing the route

Detailed description starts here. [0, 0] -> [-1, 1] -> [0, 1] -> [1, 0] -> [2, -1] -> [2, 0] -> ...

{
    vector<int> result;

    if(matrix.size() == 0 || matrix[0].size() == 0)
        return result;

    int m = matrix.size();      // rows
    int n = matrix[0].size();   // cols

    // Direction map
    vector<vector<int>> dirs = {{-1, 1},  // up direction
                                {1, -1}}; // dowm direction

    int d = 0; int row = 0; int col = 0;

    for (int i = 0; i < n*m; i ++){
        // Put the value.
        result.push_back(matrix[row][col]);

        // Each step
        row += dirs[d][0];
        col += dirs[d][1];

        // Avoid out-of-range
        if (row >= m) {
            row = m - 1;
            col += 2;
            d = 1 - d; // 0 or 1
        }

        // Avoid out-of-range
        if (col >= n) {
            col = n - 1;
            row += 2;
            d = 1 - d;
        }

        // avoid out-of-range
        if (row < 0) {
            row = 0;
            d = 1 - d;
        }

        // avoid out-of-range
        if (col < 0) {
            col = 0;
            d = 1 - d;
        }
    }
    return result;
}

Referenced by leetcode_practice().

numEquivDominoPairs()

int Dynamic_Array_Exercise::numEquivDominoPairs

(

vector< vector< int >> &

dominoes

)

Number of Equivalent dominoes Pairs - Easy.

Parameters

The	2-D dominoes vector

Returns

The number of pairs (i, j)

Complexity: O(N^2)

Ideal:

1. Search the pairs one-by-one

Test case: Input: dominoes = [[1,2],[2,1],[3,4],[5,6]] Output: 1

{
    int i, j;
    int result = 0;

    for(j = 0; j < dominoes.size() - 1 ; ++ j) {
        for (i = j + 1; i < dominoes.size() ; ++ i) {
            result += (dominoes[j][0] == dominoes[i][0] &&  dominoes[j][1] == dominoes[i][1])  ||
                    (dominoes[j][0] == dominoes[i][1] &&  dominoes[j][1] == dominoes[i][0]);
        }
    }

    return result;
}

numEquivDominoPairs_opt()

int Dynamic_Array_Exercise::numEquivDominoPairs_opt

(

vector< vector< int >> &

dominoes

)

Optimized Number of Equivalent dominoes Pairs - Easy.

Parameters

The	2-D dominoes vector

Returns

The number of pairs (i, j)

Complexity: O(N)

Ideal:

1. Using hash map and sorting the pairs
2. Count the number of equivalent pairs
3. Calculate the total of the number of equivalent pairs

Test case: Input: dominoes = [[1,2],[2,1],[3,4],[5,6]] Output: 1

{
    int result = 0;

    // hash map (key, value)
    map< pair < int, int >, int > dict;

    for(int i=0; i<dominoes.size(); i++){

        int a = dominoes[i][0], b = dominoes[i][1];

        // Sorting
        two_int key = {min(a, b), max(a, b)};

        // Count the same pair
        dict[key] += 1;
    }

    // Search hash map and calculate the arithmetic series
    for(auto it = dict.begin(); it != dict.end(); it++){
        int value = it->second;
        result += value * (value-1) / 2;
    }
    return result;
}

Referenced by leetcode_practice().

pachiraTringle()

vector< vector< int > > Dynamic_Array_Exercise::pachiraTringle

(

int

numRows

)

Print Pascal's triangle - Easy.

Parameters

The	row of Pascal's triangle

Returns

The last row of Pascal's triangle

Ideal:

1. Create first and second layer of Pascal's triangle
2. Declare new vector and storing the sum of the two numbers on the previous row

{[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1], ...}

{
    vector<vector<int>> result;

    if(numRows == 0)
        return result;

    vector<int> temp;

    // first layer
    temp.push_back(1);
    result.push_back(temp);

    if (numRows == 1)
        return result;

    // second layer
    temp.push_back(1);
    result.push_back(temp);

    if (numRows == 2)
        return result;

    // Others
    for (int i = 2; i < numRows; i ++) {
        // default value of the last Pascal's triangle is 1
        vector<int> c(i+1, 1);

        // sum of the two numbers on the previous row (total i - 1 times)
        for (int j = 1; j < i; j ++) {
            c[j] = result[i-1][j-1] + result[i-1][j];
        }
        result.push_back(c);
    }
    return result;
}

Referenced by leetcode_practice().

pivot()

int Dynamic_Array_Exercise::pivot

(

vector< int > &

nums

)

Find the pivot index - Easy.

Parameters

The	test case's vector

Returns

The pivot index

Ideal:

1. Find sum of all elements
2. Calculate left sum (sum - pre_sum - current elements) and
3. Determine whether the right sum is the same as the left sum

{
    long sum = 0;
    int left_sum = 0;

    // Find sum of all elements
    for (int n: nums)
        sum += n;

    // Compare left sum with the right sum
    for(int i = 0; i < nums.size(); i ++) {
        if(left_sum == sum - left_sum - nums[i])
            return i;
        left_sum += nums[i];
    }
    return -1;
}

Referenced by leetcode_practice().

plusOne()

vector< int > Dynamic_Array_Exercise::plusOne

(

vector< int > &

nums

)

Plus one the last position - Easy.

Parameters

The	test case's vector

Returns

The result of plus one's matrix

Ideal:

1. Plus one on the last value and distinguish whether it need to carry

Test case: Input: [1,2,3] Output: [1,2,4]

{
    int i;

    for(i = nums.size() - 1; i >= 0 ; i--) {
        // Plus one when last value is not equal to 9, otherwise carrying
        if (nums[i] != 9) {
            nums[i] ++;
            return nums;
        } else // Carry
            nums[i] = 0;
    }

    // Overflow
    if (i < 0) {
        // insert element with value 1 at 1th position in vector
        nums.insert(nums.begin(), 1);
    }

    return nums;
}

Referenced by leetcode_practice().

spiralMatrix()

vector< int > Dynamic_Array_Exercise::spiralMatrix

(

vector< vector< int >> &

matrix

)

Print Spiral Matrix - Medium.

Parameters

The	test case's matrix

Returns

The spiral matrix

Ideal:

1. Route's direction

• first row (left to right), last column (up to down),
• last row (right to left), first column (down to up)

{
    vector<int> result;

    // Protecting
    if(matrix.size() == 0 || matrix[0].size() == 0)
        return result;

    int i = 0;
    int col = 0;    // left to right
    int row = 0;    // up to down
    int m = matrix.size();      // down to up (rows)
    int n = matrix[0].size();   // right to left (columns)

    // be careful with heap-buffer-overflow issue
    while (row < m  && col < n ) {
        // first row (left to right)
        for (i = col ; i < n; ++ i) {
            result.push_back(matrix[row][i]);
        }

        // last column (up to down)
        for (i = row + 1 ; i < m ; ++ i)
            result.push_back(matrix[i][n - 1]);

        // last row (right to left) and avoid repetition
        if ((m - 1) != row) {
            for (i = n - 2 ; i >= row ; -- i) {
                result.push_back(matrix[m - 1][i]);
            }
        }

        // first column (down to up) and avoid repetition
        if ((n - 1) != col) {
            for (i = m - 2 ; i > col; -- i) {
                result.push_back(matrix[i][col]);
            }
        }

        // indicate the route's direction
         ++ row;
         ++ col;
         -- m;
         -- n;
    }
    return result;
}

Referenced by leetcode_practice().

---

The documentation for this class was generated from the following files:

• array/leetcode_practice.h
• array/leetcode_practice.cpp