A video encoding apparatus includes a data buffer and a video encoding circuit. Encoding of a first frame includes: deriving reference pixels of a reference frame from reconstructed pixels of the first frame, respectively, and storing reference pixel data into the data buffer for inter prediction, wherein the reference pixel data include information of pixel values of the reference pixels. Encoding of a second frame includes performing prediction upon a coding unit in the second frame to determine a target predictor for the coding unit. The prediction performed upon the coding unit includes: checking if a search range on the reference frame for finding a predictor of the coding unit under an inter prediction mode includes at least one reference pixel of the reference frame that is not accessible to the video encoding circuit, and determining the target predictor for the coding unit according to a checking result.