ประยุกต์กับ LeetCode

การสำรวจเวลาและ Memory ที่ใช้ใน LeetCode

สำหรับเว็บ Leet Code ตรงส่วนของ Submission เองจะมีส่วนของการบอกเวลาไว้เหมือนกัน เราสามารถดูส่วนนี้ และเทียบ Code Complexity กับเวลาได้เช่นกัน

เวลา กับ Big O

โจทย์ https://leetcode.com/problems/4sum/description/

code แบบ Time limit Exceed

class Solution {
public:
  vector<vector<int>> fourSum(vector<int> &nums, int target) {
    int n = nums.size();
    set<vector<int>> quadruplets;

    for (int i = 0; i < n - 3; i++) {
      for (int j = i + 1; j < n - 2; j++) {
        for (int k = j + 1; k < n - 1; k++) {
          for (int l = k + 1; l < n; l++) {
            if ((long long)nums[i] + nums[j] + nums[k] + nums[l] == target) {
              vector<int> quad = {nums[i], nums[j], nums[k], nums[l]};
              sort(quad.begin(), quad.end());
              quadruplets.insert(quad);
            }
          }
        }
      }
    }

    vector<vector<int>> result(quadruplets.begin(), quadruplets.end());
    return result;
  }
};

วิเคราะห์ Big O จาก code นี้ เมื่อ n คือขนาดของ Array nums

• loop ชั้นนอกสุด วนรอบ n-3 ครั้ง ดังนั้นมีความซับซ้อน O(n)
• loop ชั้นที่ 2 วนรอบ n-2 ครั้ง ดังนั้นมีความซับซ้อน O(n)
• loop ชั้นที่ 3 วนรอบ n-1 ครั้ง ดังนั้นมีความซับซ้อน O(n)
• loop ชั้นในสุด วนรอบ n ครั้ง ดังนั้นมีความซับซ้อน O(n)

เนื่องจากเป็นลูปซ้อนกัน 4 ชั้น ดังนั้นความซับซ้อนรวมของ function fourSum จึงเป็น O(n^4)

จากเคสนี้ส่งผลทำให้เกิดเคส Time Limit Exceed เกิดขึ้นเนื่องจากใช้เวลาการคำนวนที่นานเกินไป (กว่าที่โจทย์กำหนด)

code แบบผ่านเรื่องเวลา

สิ่งที่เราจะทำคือ เราจะพยายามลด Big O ของ code ลง โดย

1. การเรียงลำดับ Array nums ใช้เวลา O(n log n) โดยใช้ Algorithm การเรียงลำดับมาตรฐาน เช่น quicksort หรือ mergesort
2. มี loop เพียงแค่ 2 loop โดย loop นอกทำงาน n-3 รอบ
   • สำหรับแต่ละรอบ loop จะทำงาน n-2-i รอบ โดย i คือ index ของ loop นอก
   • loop ใน มี loop while ที่ใช้เทคนิค 2 pointer (เพิ่มตัวชี้ 2 ตัว) เพื่อหาตัวเลขอีกสองตัว ในกรณีที่แย่ที่สุด loop while นี้อาจทำงานได้ถึง O(n) รอบสำหรับแต่ละรอบของ loop ใน

เมื่อรวมสิ่งเหล่านี้เข้าด้วยกัน:

• การเรียงลำดับใช้เวลา O(n log n)
• loop ซ้อนกันมีจำนวนรอบรวมทั้งหมด (n-3) * (n-2) ซึ่งลดรูปได้เป็น O(n^2)
• สำหรับแต่ละรอบของ loop ซ้อน loop while ด้านในใช้เวลา O(n)

ดังนั้น ความซับซ้อนของเวลาโดยรวมคือผลรวมของส่วนเหล่านี้ O(n log n) + O(n^2) * O(n) = O(n log n) + O(n^3)

code ก็จะมีหน้าตาออกมาเป็นแบบนี้แทน

class Solution {
public:
  vector<vector<int>> fourSum(vector<int> &nums, int target) {
    int n = nums.size();
    vector<vector<int>> result;

    if (n < 4) {
      return result;
    }

    sort(nums.begin(), nums.end());

    for (int i = 0; i < n - 3; i++) {
      if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
      }

      if ((long long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] >
          target) {
        break;
      }

      if ((long long)nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] <
          target) {
        continue;
      }

      for (int j = i + 1; j < n - 2; j++) {
        if (j > i + 1 && nums[j] == nums[j - 1]) {
          continue;
        }

        if ((long long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
          break;
        }

        if ((long long)nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) {
          continue;
        }

        int left = j + 1;
        int right = n - 1;

        while (left < right) {
          long long sum =
              (long long)nums[i] + nums[j] + nums[left] + nums[right];

          if (sum == target) {
            result.push_back({nums[i], nums[j], nums[left], nums[right]});

            while (left < right && nums[left] == nums[left + 1]) {
              left++;
            }
            left++;

            while (left < right && nums[right] == nums[right - 1]) {
              right--;
            }
            right--;
          } else if (sum < target) {
            left++;
          } else {
            right--;
          }
        }
      }
    }

    return result;
  }
};